CF908G | 数位dp CF908G我们考虑给数字排序后一个数位的贡献。
每个数字的贡献可以表示成 $10^i$ 的形式，就是它的位置乘上 $10^i$
所以
ans = \sum_{dig} dig\times c(dig)其中 $c(i)$ 表示 这一位最后被分配到的位置置 1 所得到的一串 11…111000…00
我们给这个式子差分一下，成为了：
ans = \sum_{dig} \sum_{i\ge dig} c(i)考虑后面那一段，所有大于等于 $dig$ 的 $c(i)$ 的和，就是一串纯 1 的数 ...
阅读更多 DP 选讲 | dp - 笔记 写完了。。还有很多坑没填。。。
DP 选讲例题AGC 034 E我们考虑，如果两个棋子呈祖先关系，显然不会选择它们俩（不优秀）。否则，必然是选择两个点，它们的 dist 分别 - 1。
然后考虑可以把棋子拆成 $dist[u]$ 个棋子然后放在它到根的路上，然后相当于可以选择两个不同子树的点削除。
于是考虑枚举最后的根 $rt$ ，然后考虑它的所有子树，其中有一个最大（棋子最多的）的 $u$ ，我们考虑分类
如果当前 $sum - max \geq max$ 那么 $F[u] = \lfloo ...
阅读更多 3.8 模拟赛 A Bitset Master | 比赛 - 点分治 3.8 模拟赛 A Bitset Master题目连接
明显，我们可以用 Bitset 维护每个点的集合，复杂度是 $O(n^2 + \frac{nm}{w})$ 可以通过 50 分。
离线的那 20 分好像可以倒着合并啥的，不是很会，下面写正解了。
考虑这个询问，本质上就是从 $u$ 出发走 2 操作时刻单调递增的路径可以走到的 $v$ 的个数。先离线，把操作时刻挂在边于是我们就从一个维护点集的问题变成了一个路径问题。
考虑点分治，假设当前分治中心在 $u$ ，首先跑一次 dp ，求出从每个操 ...
阅读更多 计算几何 | 总结 - 计算几何 仍在更新中…..
计算几何没正式学过。。胎教组选手 yijan
基础操作加减乘除、点积叉积首先我们定义点，显然点的定义直接用坐标
1234struct Point { double x , y; Point( double x = 0 , double y = 0 ): x(x) , y(y) {}};
然后，一般矢量使用坐标表示，标记为 $\vec v = (x,y)$ ，直接把点看成矢量也可。
定义一下基本运算，包括向量加减、数乘：
123 ...
阅读更多 Ozon Tech Challenge 2020 简要题解 （ A ~ F ） | 比赛 CF1305 简要题解（A ~ F）场上总是想到鸡肋做法写好久啊。。CF好难 /dk
A Kuroni and the Gifts注意到数字不同，排序后输出就好了，匹配必然是递增的。
12345678910111213141516171819202122#include "iostream"#include "algorithm"#include "cstring"#include "cstdio"using nam ...
阅读更多 Hello World! | Gridea About Me在无数久的 🐦咕咕咕 后一个新博客它建成了！
由于博主懒，直接用的 Coding 和 Gridea 建的站，主题用的 Simple。
主要会放模拟赛和平时写题的题解和一些学习笔记、总结，当然也会有游记和杂文。
关于以前的文章， cnblogs 的文章应该都会导过来，第一代 Blog 的文章估计不会去找了，而且懒得一篇一篇加入分割符了，将就看一下吧 QwQ。。
Contact Me:
QQ: 1192034298
Telegram: yijan
E-Mail: yihanq ...
阅读更多 友情链接
zzh
lsj
Itst
zbww
yg
zyw
阅读更多 FMT 和 子集卷积 | 总结 - 子集卷积 - FMT FMT 和 子集卷积FMT给定数列$a_{0\dots 2^{k}-1}$求$b$满足$b_{s} = \sum_{i\in s} a_i$
实现方法很简单，
1234for( i in 0 to n-1 ) for( j in 0 to 2^n-1) if( j & ( 1 << i ) ) a[j] += a[j ^ ( 1 << i )]
然后称为$B = \text{FMT}(A)$，快速莫比乌斯变换
想要还原也很简单，把代码反着写：
1234f ...
阅读更多 2.29 讲课 笔记 | 笔记 - 容斥 - 子集卷积 - FMT 2.29 讲课 笔记开头的容斥的证明被咕咕咕了。
FMT给定数列$a_{0\dots 2^{k}-1}$求$b$满足$b_{s} = \sum_{i\in s} a_i$
实现方法很简单，
1234for( i in 0..n-1 ) for( j in 0..2^n-1) if( j & ( 1 << i ) ) a[j] += a[j ^ ( 1 << i )]
然后称为$B = FMT(A)$，快速莫比乌斯变换
想要还原也很简单，把代码反着写：
1 ...
阅读更多 Pollard-Rho 算法 | 总结 - 数论 - Pollard-Rho Pollard-Rho一种复杂度大概在$O(n^{\frac 1 4} \log n)$的分解质因数方法。
Miller-Rabin给定一个$10^{18}$范围的数，判断质数
由于费马小定理，我们知道当$a\bmod p \neq 0$且$p$为 质数 时，$a^{p-1} \equiv 1 \pmod p$，而如果$p$不为质数，这东西有一定几率成立。
所以我们有一个想法，随机一些$a$，对每个$a$用这个式子判断一下，如果有一个错误了它就直接是合数了。
但是有些合数更特殊，对于$1\leq ...
阅读更多 Count on a Tree II | 分块 Count on a Tree II以前写的用可持久化分块维护。。既难写而且常数还大。。最后在 Luogu 还是开了读优挂才跑过去的。。感觉题解区的 Bitset 维护比我这个不知道高到哪里去了。。
考虑随机在这个树上打 $\sqrt n$ 个点作为关键点，然后每个点向上跳找到第一个关键点的期望长度是 $ \sqrt n $ 的。当然，也有没那么玄学的打点方法，用深度是 $\sqrt n$ 倍数并且向下最深深度大于等于根号的点来打，这样打出来点的个数是 $\sqrt n$ 的并且明显从每个点向上 ...
阅读更多 DZY Loves Math | 数论 - 莫比乌斯反演 DZY Loves Math万年没写莫反都快不会了。。认真推一次式子吧 /kel
首先把题面写下来：
\sum_{i=1}^n\sum_{j=1}^m f(\gcd(i,j))其中$f$为素因数次幂最高的数的指数。
首先，按照莫反的套路枚举$\gcd$的值
\sum_{i=1}^n \sum_{j=1}^m \sum_{d=1}^n [gcd(i,j) = d] f(d)然后交换循环次序
\sum_{d=1}^n f(d) \sum_{i=1}^n \sum_{j=1}^m [\gcd(i ...
阅读更多 二次剩余 | 总结 - 数论 - 二次剩余 二次剩余解方程
x^2 = n定义一个数的 勒让德符号 为
\left(\frac{n}{P}\right)=\left\{\begin{array}{ll}0 & \text { if } P | n \\ 1 & \text { if } \exists a, a^{2} \equiv x(\bmod P) \\ -1 & \text { if } \text{not} \exists A a, a^{2} \equiv x(\bmod P)\end{array}\right. 我们只讨 ...
阅读更多 exCRT & 骆克强乘法 | 总结 - exCRT exCRT & 骆克强乘法只是丢两个板子啦。
exCRT的做法就是每次拿两个方程合并成一个，合并的过程推下式子就是个 exgcd。具体可以在 zjk 的 ptt 里面找到。
先放个$O(1)$慢速乘
1ll mul( ll a , ll b , ll p ) { a %= p , b %= p; return ( (a * b - (ll)( (ll)( (long double)a / p * b + 0.5 ) * p )) % p + p ) % p; }
然后 ...
阅读更多 CF585E Present for Vitalik the Philatelist | 数论 - 狄利克雷前缀和 CF 585 E Present for Vitalik the Philatelist我们假设$f(x)$表示与$x$互质的数的个数，$s(x)$为 gcd 为$x$的集合的个数。
那么显然答案就是
\sum_{i > 1} f(i)s(i)所以我们现在考虑怎么求$f$和$s$。
先考虑$f$，
f(x) = \sum_{i} [gcd(i,x) = 1] c_i\\f(x) = \sum_{i} c_i \sum_{d|gcd(i,x)} \mu(d)\\f(x) = \sum_{d | ...
阅读更多 Dirichlet 前缀和的几种版本 | 数论 - 题解 - 狄利克雷前缀和 【模板】Dirichlet 前缀和求
B[i] = \sum_{d|i} A[d]$n \le 2\times 10^{7}$
看代码：
12345for( int i = 1 ; i <= en && pri[i] <= n ; ++ i ) { for (int j = 1; j * pri[i] <= n; ++j) { B[j * pri[i]] += B[j]; } ...
阅读更多 UVA1104 芯片难题 Chips Challenge | 费用流 UVA1104 芯片难题 Chips Challenge答案最多不会超过160，可以考虑枚举答案。
当我们枚举答案并且确定每行的最大限度$maxn$时，其实是可以放多于答案个芯片的。因为此时仍然合法，只是不优秀。
现在，我们考虑第$i$行/列有$t_i$个部件，那么我们知道$0 \le t_i \le maxn$同时，
t_i = a_{i,1} + a_{i,2} + \dots + a_{i,n}\\t_i = a_{1,i} + a_{2,i} + \dots + a_{n,i}移个项， ...
阅读更多 NOI 2008 志愿者招募 | 费用流 NOI 2008 志愿者招募考虑用$p_i$表示第$i$天实际招收的人数，我们假设我们有三种志愿者，分别是$1\to 2,1 \to 3 , 2\to 3$，我们招手的人数分别是$b_1,b_2,b_3$
那么第一天实际人数就是$p_1 = b_1+b_2 \geq a_1$，同理我们把三个不等式写出来：
b_1 + b_2 \ge a_1\\b_1 + b_2 + b_3 \ge a_2\\b_2 + b_3 \ge a_3发现这是个线性规划的模型，而且据说这题玄学线性规划也能跑过去。。
然 ...
阅读更多 WC 2007 剪刀石头布 | 费用流 WC 2007 剪刀石头布看到这个三元环的问题很容易可以考虑到求不合法的三元环的数量的最小值。
什么情况不合法？既然不合法，当且仅当三元环中有一个人赢了另外两个人。所以我们考虑对于一个人而言，如果她新增加了一场胜利，并且之前赢了$k$场，那么她的非剪刀石头布的胜利次数会增加$k$个。并且这样统计每个不合法情况正好只会被统计一遍。
这里就学到了一个非常厉害的建图方法，我们从每个人到$t$连很多条边，容量都是 1 ，费用设置为$0,1,2,3,\dots$。然后从比赛向胜利者建立一条容量为 1 费用 ...
阅读更多 BZOJ 2127 Happiness | 最大流 BZOJ 2127 Happiness（默认题面是 wyy PPT里面的题面）
我们先考虑两个人的情况，如果只有两个人，考虑从$s$向它们连边，割掉表示帮，再从它们向$t$连边，表示不帮。同时如果两个人没有选择相同的行为，我们认为这样会产生损失，注意到如果两个人选择的行为不一样，如果我们把这两个人之间连一条双向边，仍然没有割掉。现在我们需要的就是确定这条双向边的权值。
我们考虑建立出来的图是这样的：
现在我们需要确定$a,b,c,d,e$的权值。
我们用$v_1$表示 同时选择帮忙的额外收益， ...
阅读更多 Codechef RIN | 最大流 Codechef RIN最大化平均分本质上就是最大化得分和。但是发现这个东西不太可做，于是规定一个 100 分的满分后就是最小化扣分的和。
对于一个课程，我们先不考虑限制问题，那么可以建立$a_1,a_2,\dots ,a_m$这$m$个点，然后$s \to a_1 , a_1\to a_2,\dots a_{m-1} \to a_m , a_m \to t$这样连，并且$a_{i-1} \to a_i$的权值就是在第$i$学期学完这门课的扣分，特别的，$a_m \to t$连$\infin$， ...
阅读更多 BZOJ 1497 [NOI2006]最大获利 | 最大流 BZOJ 1497 [NOI2006]最大获利从原点向每个中转站建立容量为$p_i$的边，再从中转站向以它作为条件的用户群建立$+\infin$的边，最后从用户群向汇点建立$c_i$的边，医院的权值和 - 最小割就是答案。
为什么这样是对的呢？考虑我们满足一个用户组的需求，无非就是不要这个需求（割掉这个边）或者花代价去割掉它的$A_i,B_i$，这样做它的盈利是$c_i - p_a-p_b$。所以最后求和 c 减去最小割就是答案。
12345678910111213141516171819202 ...
阅读更多 UVA 10779 Collectors Problem | 最大流 UVA 10779 Collectors Problem我们考虑对所有徽章建一排点，然后从徽章连向 T 建立限制为 1 的边，然后从 S 到每种徽章建立我们拥有数量的点。
然后考虑对别人交换，从每种徽章连向没有这种徽章的人，容量限制是 1 ，再从每个人连向它拥有个数大于 1 的徽章，容量是它的徽章数 - 1。
这样建图跑最大流就做完啦。
12345678910111213141516171819202122232425262728293031323334353637383940414243444 ...
阅读更多 CF932F Escape Through Leaf | dp - 李超线段树 CF932F Escape Through Leaf首先，$O(n^2)$dp 是很显然的，方程长这样：
dp[u] = min\{dp[v] + a_u\times b_v\}这个方程看起来就很斜率，当我们写成了斜率优化的形式大概是这样的：
\frac{dp[v]-dp[j]}{a_v-a_j} < -b_u我们想通过这个式子做就必须维护动态凸包以及凸包的合并。这个东西是很恼火的，可能用 set 和 splay 啥的可以搞，可惜不大会。
这里就引入了一种科技，李超线段树。
李超线段树是一种 ...
阅读更多 CF1278F Cards | dp - 期望 CF1278F Cards首先我们知道，一次拿牌的概率是$P(i) = \frac 1 m$，同时权值是1，所以期望就是$\frac{1} m$，拿$n$次牌贡献是独立的，就是$\frac n m$。
但是我们要算的是$k$次方的期望，众所周知期望的二次方不等于二次方的期望。我们考虑$E$的意义，$E$在这一次拿到 Joker 的$\frac 1 m$的概率下是 1 ，其他情况是0。则$E^2$就是随机两次，这两次都是 1 的情况下是 1 ，其他情况是0。
我们把这$n$次是否抓到 Joker ...
阅读更多 模版 动态 dp | dp - 总结 - 动态dp - LCT 模版 动态 dp终于来写这个东西了。。
LG 模版：给定 n 个点的数，点有点权，$m$次修改点权，求修改完后这个树的最大独立集大小。
我们先来考虑朴素的最大独立集的 dp
dp[u][0] = \sum_v max\{dp[v][1],dp[v][0]\}\\dp[u][1] = val[u] + \sum_v dp[v][0]现在我们就拥有了一个$O(nm)$的做法，但是明显它不优秀。
既然支持修改，我们可以考虑树剖（或者LCT），现在树被我们剖成了重链和轻链。此时发现我们其实可以先对轻 ...
阅读更多 「LibreOJ NOI Round #2」不等关系 | NTT - dp - 容斥 「LibreOJ NOI Round #2」不等关系暑假 dls 讲过但是当时掉线了。。
考虑我们如果直接无视 > 符号，现在这个排列就一定是一些下降的子段组合在一起的。我们假设这些段的长度分别是$a_1,a_2,\dots ,a_k$那么算出来方案数量是
\frac{n!}{a_1!a_2!\dots a_k!}因为我们可以任意定一个排列，为了满足条件只需要把这些子段排个序。理解一下发现就是这个东西。
但是我们还有 > 符号啊，既然不好处理，我们可以考虑容斥，比如， <& ...
阅读更多 [HNOI2013]游走 | dp - 期望 [HNOI2013]游走考虑随机游走时一条边$(x,y)$被经过，只有两种情况，要么是我们走到了点$x$，然后随机钦定了$y$，要么就是反过来。我们假设一个点的度数为$deg[i]$，假设一个点期望会经过$t[u]$次，所以一个边所贡献的权值就是$w \times ( \frac{t[x]}{deg[x]} + \frac{t[y]}{deg[y]} )$。
所以现在我们的目标就是求$t$。发现$n \leq 500$我们可以考虑高消，具体而言，可以列出
t[u] = \sum \frac{t ...
阅读更多 Yet Another Minimization Problem | dp - 分治 - 决策单调性 Yet Another Minimization Problem一个很显然的决策单调性。
方程是很显然的$f_i = \min\{f_{j-1} + w(j,i)\}$。
它具有决策单调性，可以参考钟神的 Blog
我们考虑怎么实现这个东西，按照上次 DLS 讲的，考虑 solve(l,r,L,R) 表示 我们当前在处理$l,r$的$dp$ 值，我们知道当前决策点在$L,R$内。
然后考虑怎么求，先对$mid$暴力跑出决策位置，然后分治 solve(l,mid-1,L,op),solve(mid ...
阅读更多 