一些常用的结论
1、(Hall)定理推论:最大匹配数=(|X|)-(max(|W|-|next(W)|,……,0))
其中(X)是左部分的点集,(|W|)是(X)中的一个点集,(N(W))为(W)的所有邻居(二分图上)
2、关于莫比乌斯反演
整出分块降复杂度
[l=min(n(n/l),m/(m/l))\
r=l+1\
l不一定从1开始
]
莫比乌斯反演
[F(n)=sum_{n|d}f(d)\
f(n)=sum_{n|d}F(d)*mu(frac{d}{n})\
F(n)=sum_{d|n}f(d)\
f(n)=sum_{d|n}F(frac{n}{d})*mu(d)\
这些式子不能交换F和mu的位置\
d(ij)表示i*j的约数个数和 \
d(i*j)=sum_{x|i}sum_{y|j}[gcd(x,y)==1]
]
证明:
[d(i*j)=sum_{x|i}sum_{y|j}[gcd(x,y)==1]
]
我们考虑把每个因子一一映射。
如果(i*j)的因子(k)中有一个因子(p^c)，(i)中有因子(p^a)，(j)中有因子(p^b)。我们规定：
- 如果 (cle a)，那么在 (i)中选择。
- 如果 (c>a)，那么我们把(c)减去(a)，在(j)中选择(p^{c-a})（在 (j) 中选择 (p^e) 表示的是 (p^{a+e})）
对于 (i*j)的因子 (k) 的其他因子同理。于是对于任何一个 (k) 有一个唯一的映射，且每一个选择对应着唯一的 (k)。
通过如上过程，我们发现：对于 (i*j) 的因子 (k=prod {p_i}^{c_i})，我们不可能同时在 (i)和 (j)中选择 (p^e)（优先在 (i) 中选择，如果不够就只在 (j) 中选择不够的指数），故 (x) 和 (y) 必须互质。
等式得证。----from Luogu Siyuan
一些经验:杜教筛递归时尽可能减少递归次数
杜教筛常用技巧
[mu*I=e\
mu*Id=varphi\
varphi*I=Id\
上面是卷积\
sum_{i=1}^n i=frac{n*(n+1)}{2}\
sum_{i=1}^n i^2=frac{n*(n+1)*(2*n+1)}{6}\
sum_{i=1}^n i^3=(sum_{i=1}^n i)^2=(frac{n*(n+1)}{2})^2\
]
杜教筛套路:
[S(n)=sum_{i=1}f(i)\
sum_{i=1}^n(f*g)(i)= sum_{i=1}^nsum_{d|i}f(d)g(i/d)=sum_{d=1}^ng(d)*sum_{d|i}f(frac{i}{d})=sum_{d=1}^ng(d)*sum_{i=1}^ leftlfloorfrac{n}{d}
ight
floor f(i)\
g(1)S(n)=sum_{i=1}^n(f*g)(i)-sum_{i=2}g(i)S(leftlfloorfrac{n}{i}
ight
floor )这个式子就是常用的了
]
遇到过的一个模型:
[f(i)=varphi(i)i^2,我们令g(i)=i^2\
sum_{i=1}^n(f*g)(i)=sum_{i=1}^nsum_{d|i}varphi(d)*d^2*(frac{i}{d})^2=sum_{i=1}^ni^2*sum_{d|i}varphi(d)=sum_{i=1}^ni^3\
g(1)S(n)=sum_{i=1}(g*f)(i)-sum_{i=2}g(i)S(leftlfloorfrac{n}{i}
ight
floor)\
f(i)=varphi(i)i同理,令g(i)=i\
(f*g)(i)=i^2
]
结论补充:
[sum_{i=1}^n[gcd(i,n)==1]i=frac{varphi(n)*n+[n==1]}{2}\
证明:当nge2时,若gcd(i,n)==1则有gcd(n-i,n)==1,而与n互质的数有varphi(n)项,\那就是一个首项加末项*项数/2\记得特判n=1
]
由莫比乌斯函数前缀和性质:
[sum_{i=1}^nsum_{d|i}mu(d)=1\
sum_{i=1}^nmu(d)lfloor frac{n}{d}
floor=1\
]
关于求逆元:如果有(n)个已知的待求逆元的数,可以用类似求阶乘的方法预处理出每个数的逆元 (O(n))
3、inplace_merge函数
包含在 (algorithm) 头文件
一个数组(a),假设存在分界点(mid),保证(mid)两端排序方式相同
使用:inplace_merge((a+L,a+mid,a+R,cmp))
(cmp)没有默认按值升序，
操作区间:([a+L,a+mid),[a+mid,a+R)),左开右闭
inplace_merge,在分配缓存成功时,时间复杂度(O(M+N)),空间复杂度看分配的缓存,即可能为(O(M)),(O(N))或(O(M+N)),否则,时间复杂度为(O(Nlog(N))),空间复杂度为(O(1))
保证合并的两个部分的原有元素顺序不
4、二项式定理
[inom{n}{m}=frac{n!}{m!*(n-m)!}\
F(n)=sum_{i=0}^n inom{n}{i}G(i)\
反演:G(n)=sum_{i=0}^n (-1)^{n-i} inom{n}{i}F(i)\
F(n)=sum_{i=k}^n inom{i}{k}G(i)\
反演:G(n)=sum_{i=k}^n (-1)^{i-k} inom{i}{k}F(i)
]
来看一些二阶(?)的情况
[f(n,m)=sum_{i=0}^nsum_{j=0}^minom{n}{i}inom{m}{j}g(i,j)\
g(n,m)=sum_{i=0}^nsum_{j=0}^m(-1)^{n-i+m-j}inom{n}{i}inom{m}{j}f(i,j)\
----分割线----\
f(i,j)=sum_{x=i}^nsum_{y=j}^minom{x}{i}inom{y}{j}g(x,y)\
g(i,j)=sum_{x=i}^nsum_{y=j}^m(-1)^{x-i+y-j}inom{x}{i}inom{y}{j}f(x,y)
]
5、常见的定义
完全祖先/后代:不包括自身的祖先/后代
6、一堆结论
在一个半径为(R)的圆内等概率走,欧几里得距离的平方的期望是(frac{R^2}{2})
[S=sum_{i=1}^ni*[gcd(i,n)=1]\
S+S=sum_{i=1}^ni*[gcd(i,n)==1]+sum_{i=1}^n(n-i)*[gcd(n-i,n)==1]=n*varphi(n)\
S=(n*varphi(n)+[n=1])/2
]
欧拉函数(sqrt{n})时间内利用积性函数性质求,(varphi(p^k)=p^k-p^{k-1}),还可以提前筛出质因子加速51nod1363
可以用来化式子 (lfloor frac{x}{2}
floor+lceil frac{x}{2}
ceil=x)
定义一个新函数(msf(n)=max_{d^2|n} d),即(n)的最大平方因子,容易想到有:
[mu(n)^2=[msf(n)==1]=sum_{d|msf(i)}mu(d)\
d|msf(i)等价于d^2|i\
如果外面还有其他项,就可以通过变换推式子了 loj6181讨论区
]
一个超大质数((hash)防冲突?)
[10000000000000061=1e16+61
]
欧拉回路注意起点的循环同构现象
7、不太常用的latex公式
(
ightarrow)
(cdot)
(in)
(mathbb{N})
(pm)
(
e)
(infty)
(sqrt[3]{6})
$Leftrightarrow $
({}_1^2!X)左部上下标
屏幕放大或缩小ctrl+shift+ 上面一排那个数字后面的+ - 号
8、决策单调性优化:四边形不等式
称一个二维序列(f)满足四边形不等式,当且仅当:$ forall a<ble c<d,a,b,c,din mathbb {N}^+,f_{a,d}+f_{b,c} ge f_{a,c}+f_{b,d}$
推导:
(forall a<b,a,bin mathbb{N}^+,f_{a,b+1}+f_{a+1,b}ge f_{a,b}+f_{a+1,b+1})
(f_{a,b+1}-f_{a,b}ge f_{a+1,b+1}-f_{a+1,b})
(f_{a,b+1}-f_{a,b}ge f_{a+i,b+1}-f_{a+i,b})
最后有这个结论:$ f_{a,b+j}-f_{a,b}ge f_{a+i,b+j}-f_{a+i,b}$
9、斐波拉契数列(我的弱项)
广义(?)斐波拉契数列:
[5,-3,2,-1,1,|0,1,1,2,3,5\
对于i<0 f_i=-1^{i+1}f_{-i}
]
斐波拉契数列
[F_0=0,F_1=1\
F_n=F_kF_{n-k+1}+F_{k-1}F_{n-k}\
F_n=F_2F_{n-1}+F_1F_{n-2}=F_{n-1}+F_{n-2}\
F_{k-1}^2+F_{k-1}F_{k}-F_k^2=(-1)^k
]
矩阵乘法:矩阵乘法只满足结合律,不满足交换律
[初始矩阵\
egin{vmatrix}
1&1\
1&0
end{vmatrix}\
单位矩阵\
egin{vmatrix}
1&0\
0&1
end{vmatrix}\
初始矩阵可以看作\
egin{vmatrix}
f_2&f_1\
f_1&f_0
end{vmatrix}\
初始矩阵的n次方\
egin{vmatrix}
f_{n+1}&f_n\
f_n&f_{n-1}
end{vmatrix}
]
要背的结论:在(mod ext{ }1e9+9)的意义下,(sqrt{5})的二次剩余是383008016
斐波拉契数列的生成函数(F(x)=frac{x}{1-x-x^2})
卡特兰数的生成函数(H(x)=frac{1- sqrt {1-4x} }{2x},H(0)=1)
牛顿二项式定理:
[inom{n}{k}=frac{r^underline{k}}{k!}\
rin C(复数域),kin N\
(1+x)^alpha=sum_{n>=0}inom{alpha}{n}x^n
]
普通生成函数(OGF)
[对于a_n=<1,2,3,4...>\F(x)=sum_{nge0}(n+1)x^n=sum_{nge1}nx^{n-1}=sum_{nge0}(x^n)'=(frac{1}{1-x})'=frac{1}{(1-x)^2}\
对于a_n=inom{m+n}{n}\F(x)=sum_{nge0}inom{n+m}{n}x^n=frac{1}{(1-x)^{m+1}}\
对于a_n=<1,0,1,0,1,...>\
F(x)=sum_{nge0}x^{2n}=frac{1}{1-x^2}\
同理a_n=<0,1,0,1,0...>\
F(x)=sum_{nge0}x^{2n+1}=frac{x}{1-x^2}
]
指数生成函数(EGF)
[F(x)G(x)=sum_{ige0}a_ifrac{x^i}{i!}sum_{jge0}b_jfrac{x^j}{j!}\=sum_{nge0}x^nsum_{i=0}^na_ib_{n-i}frac{1}{i!(n-i)!}\=sum_{nge0}frac{x^n}{n!}sum_{i=0}^ninom{n}{i}a_ib_{n-i}
\
sum_{nge0}frac{x^n}{n!}=e^x
\
sum_{nge0}frac{a^nx^n}{n!}=e^{ax}(整体代换理解)
]
长度为(n)的排列数的EGF
[F(x)=sum_{nge0}frac{n!x^n}{n!}=sum_{nge0}x^n=frac{1}{1-x}
]
(n)个数的圆排列的EGF(第一类斯特林数——列)
[G(x)=sum_{nge1}frac{(n-1)!x^n}{n!}=sum_{nge1}frac{x^n}{n}=-ln(1-x)=ln(frac{1}{1-x})
]
容易发现(exp(G(x))=F(x)),可以理解成一个排列的数(i)向(realpos_i)连边,形成若干个置换环
错排数,不存在在长度为1的置换环
[sum_{nge2}frac{x^n}n=-ln(1-x)-x\
Ans(x)=exp(-ln(1-x)-x)
]
get新姿势:51nod1728,一个不可重集大小为(s),构造映射函数(f(i)=j),一组递归函数可解当且仅当在有限次操作后存在(f(f(f(...f(x)...))=x',f(x')=x')可解的递归函数恰好有((s+1)^{s-1})种
不动点
[<Empty space Math space Block>
]
10、斯特林数总结(我的弱项)
上升幂
[x^overline{n}=x*(x+1)*(x+2)...*(x+n-1)=frac{(x+n-1)!}{(x-1)!}
]
下降幂
[x^underline{n}=x*(x-1)*(x-2)...*(x-n+1)=frac{x!}{(x-n)!}
]
上升幂下降幂的转换
[x^underline{n}=(-1)^n(-x)^overline{n}\x^overline{n}=(-1)^n(-x)^underline{n}\
]
第一类斯特林数(S1(n,k))表示的是将(n)个不同元素构成(k)个圆排列的数目,
其中一个应用:划分数字后每个划分取最值(圆排列)的排列数
[egin{bmatrix}n\kend{bmatrix}=egin{bmatrix}n-1\k-1end{bmatrix}+(n-1)*egin{bmatrix}n-1\kend{bmatrix}
]
第二类斯特林数(S2(n,k))表示的是把(n)个不同元素划分到(k)个集合的方案数(组合数)
[egin{Bmatrix}n\kend{Bmatrix}=egin{Bmatrix}n-1\k-1end{Bmatrix}+k*egin{Bmatrix}n-1\kend{Bmatrix}
]
第二类斯特林数的应用:组合数意义(超重要)
[n^m=sum_{k=0}^megin{Bmatrix}m\kend{Bmatrix}inom{n}{k}k!
]
(m)个数(in[1,n]),有(n^m)种方案,枚举有(k)个不等价类各有多少方案
二项式反演一下
[k!egin{Bmatrix}m\kend{Bmatrix}=sum_{i=0}^k(-1)^{k-i}inom{k}{i}i^m
]
推式子可以用到的结论:
求杨辉三角一列的和
[sum_{i=L}^Rinom{i}{L}=inom{R+1}{L+1}
]
[prod_{i=1}^m(1-ix)=reverse(prod_{i=1}^m(x-i))
]
快速求第二类斯特林数——行
[egin{Bmatrix}m\kend{Bmatrix}=frac{1}{k!}sum_{i=0}^k(-1)^{k-i}frac{k!}{i!(k-i)!}i^m\=sum_{i=0}^kfrac{(-1)^{k-i}}{(k-i)!}frac{i^m}{i!}
]
第二类斯特林数——列(EGF)
[k!sum_{i=0}^{infty}frac{x^i}{i!}=(e^x-1)^k
]
关于第二类斯特林数——列(EGF)提供,另一种分治写法
[H(n)=sum_iegin{Bmatrix}i\nend{Bmatrix}x^i=sum_i(negin{Bmatrix}i-1\nend{Bmatrix}+egin{Bmatrix}i-1\n-1end{Bmatrix})x^i\=nsum_iegin{Bmatrix}i-1\nend{Bmatrix}x^i+sum_iegin{Bmatrix}i-1\n-1end{Bmatrix}x^i
\H(n)=nxH(n)+xH(n-1) \H(n)=frac{x}{1-nx}H(n-1)\ H(n)=frac{x^n}{prod_i 1-ix} \H(0)=1
]
斯特林数与阶乘之间的关系
通常幂转下降幂(第二类斯特林数)
[n^m=sum_{k=0}^megin{Bmatrix}m\kend{Bmatrix}inom{n}{k}k!\=sum_{k=0}^megin{Bmatrix}m\kend{Bmatrix}n^underline{k}
]
上升幂转第一类斯特林数
[x^overline{n}=sum_{k}^negin{bmatrix}n\kend{bmatrix}x^k
]
第一类斯特林数——行(倍增)
[\O(2nlogn)
\由上升幂转通常幂可知,我们要求x^overline{n}
\考虑x^overline{2n}=x^overline{n} (x+n)^overline{n}
\如果知道f(x)可以推出f(x+k),然后二项式定理拆开这个OGF发现可以ntt优化
]
第一类斯特林数——列
先提供一种分治(O(nlog^2n))做法
套路:(1)个第一类斯特林数的母函数是(f),则(k)个的母函数是(f^k)
设单个圆排列的(EGF)是(f=sum{(i-1)!frac{x^i}{i!}}=sum{frac{x^i}{i}}),对这个倍增做(log(k))次长度位(n)的(ntt)就可以了
补个最后操作的式子 (frac{n!}{k!}prod_{sum{a_i}=n}frac{(a_i-1)!}{a_i!})
补个坏消息,被卡了.其他写法先鸽这吧
斯特林反演
[f(n)=sum_{k=0}^negin{Bmatrix}n\kend{Bmatrix}g(k)Leftrightarrow g(n)=sum_{k=0}^n (-1)^{n-k} egin{bmatrix}n\kend{bmatrix}f(k)
]
互逆操作
[sum_{k=m}^n(-1)^{n-k}egin{bmatrix}n\kend{bmatrix}egin{Bmatrix}k\mend{Bmatrix}=[n==m]\sum_{k=m}^n(-1)^{n-k}egin{Bmatrix}n\kend{Bmatrix}egin{bmatrix}k\mend{bmatrix}=[n==m]
]
下降幂推导,证明考虑(j^i)整体下移
[(j-1)^underline{i-1}=frac{j^underline{i}-(j-1)^underline{i}}{i}
]
11、多项式推式子用
[由泰勒展开:\
e^x=sum_{i=0}^{infty}frac{x^i}{i!}\
[x^k]表示多项式中x^k这一项的系数\
sum_{v=0}^n v^k=sum_{v=0}^n[x^k]e^{vx},这里可以等比数列求和\
]
[ln(frac{1}{1-(ax)^v})=sum_{j=1}^inftyfrac{1}{j}(ax)^{vj}
\先求导再积分的结果
]
麦克劳林级数
[sum_{i=0}^infty frac{x^i}{i!}=e^x
]
定和取模中学到的技巧 gym102586e Count Modulo 2
[对于多项式f(x)和质数p:f^p(x)equiv f(x^p) ext{ } (mod ext{ }p)\展开归纳可得\
类似还有f^{p^k}(x)equiv f(x^{p^k}) ext{ } (mod ext{ }p)
]
[sum_{i=0}x^i=frac{1}{1-x}中的x可以整体替换成替他值,例如ax,x+x^2
]
12、凸包
叉积:给定两个向量(vec{a}=(x_1,y_1)),(vec{b}=(x_2,y_2)),(vec{a} imes vec{b}=|vec{a}| imes|vec{b}| imes sin heta=x_1y_2-x_2y_1)
凸包上应用:
(vec{a} imesvec{b}>0)等价于(vec{b})在(vec{a})的逆时针180度内
(vec{a} imesvec{b}<0)等价于(vec{b})在(vec{a})的顺时针180度内
(vec{a} imesvec{b}=0)等价于(vec{b})和(vec{a})共线(同向或反向)
叉积和三角形面积:
(S=frac{1}{2}vec{a} imesvec{b}=frac{1}{2}|vec{a}| imes|vec{b}| imes sin heta=frac{1}{2}(x_1y_2-x_2y_1))
应用:解析几何和计算几何(计算凸包直径:旋转卡壳)
一般使用叉积建议把角度控制在180度内方便理解和处理
wqs二分:费用流是凸的.
13、高精度
含大数组的结构体(如高精)不要定义太多次,多写重载,调用({}^*this)
14、树的性质
直接在(n^{n-2})种树((prufer)序列)里面随机树高是(O(sqrt n)),
如果用给(2) ~ (n)依次在(1) ~ (i-1)里随机一个父亲,则树高期望是(O(log(n))),这种建法的方案数是((n-1)!)
对于树(森林):连通块个数=点数-边数
最小生成树:平面图和其对应的对偶图的(MST)数量相等,因为每一个平面图的生成树可以映射到对偶图上。具体的:对偶图上夹着平面图生成树边的两个平面不能通过这条边相连.
树的直径性质:设树上一个点集的直径端点为(a,b),另一点集的直径端点为(c,d),则两个点集的并的直径端点必然是(a,b,c,d)其中两个
如果一棵子树里钦定某个点(i)做根,概率是(frac{1}{sz_i}),这个可以扩展到加权的情况,如果一个序列里要求一个数(i)在最前面出现,则有概率是(frac{val_i}{sum val})
15、图
平面图性质:(mle3n-6)(边数(le)点数*3-6)
欧拉定理:
对于连通图:(V+F-E=2)(点数+面数-边数=2)
对于仙人掌(森林):连通块个数=点数-边数+环数
16、字符串
结论:一颗无根树上任意一条路径必定可以在以某个叶节点为根时,变成一条从上到下的路径(利于广义( ext{ SAM}) 的使用)
17、计数问题
对于图上两点((a,b),(c,d)),如果是一般的往右和往上移动,方案数为
[inom{c-a+d-b}{c-a}
]
但如果是往(4)个方向移动(len)步,对坐标轴旋转45度,方案数则为
[inom{len}{frac{1}{2}(len+c-a+d-b)}*inom{len}{frac{1}{2}(len+c-a+b-d)}
]
应该也可以组合数枚举(len)步内的其中三个方向操作的位置
18、 FWT（快速沃尔什变换）
思来想去决定背下来
首先要让数组长度是(2^n),若(n=0)
[FWT(A)=A
]
对于任意运算符号都有,同时都满足结合律和交换律
[FWT(A+B)=FWT(A)+FWT(B)=sum_{j=1}^{2^i}A_j+B_j\
]
按位或:
[FWT(A)=FWT(A_0),FWT(A_0+A_1)\
UFWT(A')=UFWT(A_0'),UFWT(A_1'-A_0')
]
(A_0,A_1)是(2^{i-1})时的答案,操作时认为(A_0)是(2^i)的低位部分,(A_1)是(2^i)的高位部分,这里的操作可以看成把数组前后两部分顺序接起来
按位与:
[FWT(A)=FWT(A_0+A_1),FWT(A_1)\
UFWT(A')=UFWT(A_0'-A_1'),UFWT(A_1')
]
亦或:
[FWT(A)=FWT(A_0+A_1),FWT(A_0-A_1)\
UFWT(A')=frac{UFWT(A_0'+A_1')}{2},frac{UFWT(A_0'-A_1')}{2}
]
同或:(字面意思)
[FWT(A)=FWT(A_1-A_0),FWT(A_1+A_0)\
UFWT(A‘)=frac{UFWT(A_1'-A_0')}{2},frac{UFWT(A_1'+A_0')}{2}
]
19、建图小技巧
遇到奇怪的建图方法可以考虑借鉴分层图,运用一种电梯升降的写法把边权间的关系表现出来,具体来说要在电梯的每一层提供足够的可行转移,提供一层转入,一层转出,可能再有一层中转.
另外还有笛卡尔树,K-D tree,线段树,主席树优化建图,用于处理一些特殊的问题
20、树状数组维护等差数列(痛点)
没事，暂时可以用线段树维护,记住我的维护方法首项是0,区间覆盖时要手算一下
21、扩展欧拉定理
一般的欧拉定理 对于质数(p),有(a^{varphi(p)}equiv 1(mod ext{ }p))
扩展欧拉定理,考虑对任意正整数(p)取模,(a)是任意整数
如果(gcd(a,p)=1),有(a^xequiv a^{x ext{ }mod ext{ }varphi(p)})
如果(gcd(a,p)
e1),有(a^xequiv a^{x ext{ }mod ext{ }varphi(p)+varphi(p)}),
可以简写成(a^xequiv a^{x ext{ }mod ext{ }varphi(p)+varphi(p)} ext{ }(mod ext{ }p)),上式成立前提是(x>=varphi(p))
22、好用的编译命令
g++配置:windows中输入“系统变量”——>“环境变量”——>“Path”(”Stu的用户变量“,也可以带上“系统变量”)——>“新建”——>C:Program Files (x86)Dev-CppMinGW64in 复制这段
一些编译命令:
g++ -v(这是一个返回参数,一般题目会给)
fc 文件比较(一般对拍用)
cd 跳转到某个目录(如 cd C:Program Files (x86)Dev-CppMinGW64in )
cd.. 跳到上一个目录
鼠标右键可以粘贴
对拍时直接调用exe文件,如果对拍结果闪掉(窗口出结果后直接关)可以考虑在交互库加上.out的文件输出
23、矩阵树定理
矩阵树定理求的是:
[sum_{T}prod_{ein T}w_e
]
变元矩阵树定理:
把度数矩阵设成与(i)相连的边的权值
把邻接矩阵设成边权负值
24、奇知增
devc++里的英文输入法要用"半角"
25、最小割树
先记结论:类似于分治,在当前点集种选择任意两个点作为源点、汇点，跑最小割G
两个点之间连树边，边权为G
把当前点集中和(S)连通的放进一个集合,和(T)连通的放进一个集合,分治下去
注意：每次跑最小是在全局跑,有(n-1)次最小割((n-1)跳边)
建出树之后,任意两点的最小割,就是两点树上路径的边权最小值