math

ACM 中的数学模版

前言

不知道怎么就成为数学手了(大概

Trick

切比雪夫转曼哈顿

对平面两点 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2)

曼哈顿距离:x1x2+y1y2\left|x_1-x_2\right|+\left|y_1-y_2\right|

切比雪夫距离:max(x1x2,y1y2)\max(\left|x_1-x_2\right|,\left|y_1-y_2\right|)

(x,y)(x,y) 映射到 (x+y,xy)(x+y,x-y) ,可以将曼哈顿距离映射到切比雪夫距离

(x,y)(x,y) 映射到 (x+y2,xy2)(\frac{x+y}{2},\frac{x-y}{2}),可以将切比雪夫距离映射到曼哈顿距离

已经证明不可推广至高维


组合数学

多重集的排列数(多重组合数)

S={n1a1,n2a2,,nkak}S=\{n_1\cdot a_1,n_2 \cdot a_2,\dots,n_k\cdot a_k\} 表示 n1n_1a1a_1n2n_2a2a_2\dotsnkn_kaka_k 构成的多重集,则 SS 的全排列个数为

n!i=1kni!\frac{n!}{\prod_{i=1}^k n_i!}

定义多重组合数:

(nn1,n2,,nk)=(nn1)(nn1n2)(nknk)=n!i=1kn!\binom{n}{n_1,n_2,\dots,n_k}=\binom{n}{n_1}\binom{n-n_1}{n_2}\dots\binom{n_k}{n_k}=\frac{n!}{\prod_{i=1}^kn!}

多重集的组合数

S={n1a1,n2a2,,nkak}S=\{n_1\cdot a_1,n_2 \cdot a_2,\dots,n_k\cdot a_k\} 表示 n1n_1a1a_1n2n_2a2a_2\dotsnkn_kaka_k 构成的多重集,定义从 SS 中选择 rr 个元素组成一个多重集的方案数为多重集的组合数

rmininir\le \min\limits_i n_i,方案数为

(n+k1k1)\binom{n+k-1}{k-1}

等价于 xi=rx_i=r 的非负整数解个数,多重集 {r0,(k1)1}\{r\cdot 0,(k-1)\cdot 1\} 的排列数等

r>mininir> \min\limits_i n_i

SiS_i 表示(至少)满足 xinix_i\le n_i 的方案集合( xix_i 表示从选择了 xix_iaia_i ),UU 为不存在限制的全集,则

i=1kSi=Ui=1kSi\left|\bigcap_{i=1}^kS_i\right|=\left|U\right|-\left|\bigcup_{i=1}^k\overline{S_i}\right|

由容斥

i=1kSi=iSii<jSiSj+i<j<lSiSjSl++(1)(k+1)i=1kSi\left|\bigcup_{i=1}^k\overline{S_i}\right|=\sum_i \left|\overline{S_i}\right|-\sum_{i<j}\left|\overline{S_i}\cap\overline{S_j}\right|+\sum_{i<j<l}\left|\overline{S_i}\cap\overline{S_j}\cap\overline{S_l}\right|+\dots+(-1)^{(k+1)}\left|\bigcap_{i=1}^kS_i\right|

S\overline{S} 的交是简单的,所以考虑这样容斥,我们可以钦定在集合中已经选择 x+1x+1aa,则

i=1kSi=i=1k(k+rni2k1)i<j(k+rninj3k1)++(1)k+1(k+ri=1knik1k1)\left|\bigcup_{i=1}^k\overline{S_i}\right|=\sum_{i=1}^k\binom{k+r-n_i-2}{k-1}-\sum_{i<j}\binom{k+r-n_i-n_j-3}{k-1}+\dots+(-1)^{k+1}\binom{k+r-\sum_{i=1}^kn_i-k-1}{k-1}

则原式有

i=1nSi=P(1)P(k+ri=1PnpiP1k1)\left|\bigcap_{i=1}^n S_i\right|=\sum_{P}(-1)^{|P|}\binom{k+r-\sum_{i=1}^{|P|}n_{p_i}-|P|-1}{k-1}

PP 为从整数 11kk 中任取若干项组成的递增数列

生成函数练习 1

留坑

错排问题

fnf_n 表示大小为 nn 的满足 piip_i\not=i 的排列 PP 的个数,那么有

fn=(n1)(fn1+fn2),f1=0,f2=1f_n=(n-1)(f_{n-1}+f_{n-2}),f_1=0,f_2=1

(n1)fn1(n-1)f_{n-1} 表示位置 nn 与前面 n1n-1 长的错排中任意一个已经存在的位置交换

(n1)fn2(n-1)f_{n-2} 表示位置 nn 与钦定的某个满足 px=xp_x=x 的位置 xx (共 n1n-1 种) 交换

可以证明,存在且仅存在此两种单次交换可以构造大小为 nn 的错排

容斥练习 1

设排列的全集为 UU,(至少)满足 piip_i\not=i 的排列集合为 SiS_i,则我们需要求解 Si\left|\bigcap S_i\right|,又

Si=USi\left|\bigcap S_i\right|=|U|-\left|\bigcup\overline{S_i}\right|

则转化为求 Si\left|\bigcup \overline{S_i}\right|

我们发现,利用容斥展开后,实际上要求 kSai\left|\bigcap\limits^k \overline{S_{a_i}}\right|,而此式子的值仅跟参与交的集合的个数有关,与集合的选择无关(值得一题的是,这点在容斥中很重要),在这个具体问题中值为 (nk)!(n-k)!,那么有

Si=k=1n(nk)(1)k1(nk)!\left|\bigcup\overline{S_i}\right|=\sum_{k=1}^n \binom{n}{k}(-1)^{k-1}(n-k)!

Si=k=0n(nk)(1)k(nk)!=n!k=0(1)kk!\begin{aligned} \left|\bigcap S_i\right|&=\sum_{k=0}^n\binom{n}{k}(-1)^k(n-k)!\\ &=n!\sum_{k=0}\frac{(-1)^k}{k!} \end{aligned}

组合恒等式

二项式定理及其推论

nn 为非负整数时

(i=1txi)n=(i=1tni)=n,ni>0(nn1,n2,,nt)j=1txjnj\left(\sum_{i=1}^tx_i\right)^n=\sum_{(\sum\limits_{i=1}^tn_i)=n,n_i>0}\binom{n}{n_1,n_2,\dots,n_t}\prod_{j=1}^tx_j^{n_j}

t=2t=2 ,得到一般式

(a+b)n=k=0n(nk)akbnk(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k}

a=b=1a=b=1 ,有

2k=k=0n(nk)2^k=\sum_{k=0}^n\binom{n}{k}

a=1,b=1a=1,b=-1,有

i=0n(1)i(ni)=[n=0]\sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]

即奇项和与偶项和相等

扩展:当 nn 为实数且 kk 为非负整数时,定义

(nk)=rkk!\binom{n}{k}=\frac{r^{\underline{k}}}{k!}

多项式求导

i=0ni(ni)=n2n1i=0ni2(ni)=n(n+1)2n2\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}\\ \sum_{i=0}^n i^2\binom{n}{i}=n(n+1)2^{n-2}

斯特林数练习 1

i=0n(ni)ik=j=1k{kj}nj2nj\sum_{i=0}^n\binom{n}{i}i^k=\sum_{j=1}^k{k \brace j}n^{\underline j}2^{n-j}

留坑,此题为 CF 932 E

范德蒙德卷积

i(ni)(mmi)=(m+nm)\sum_{i}\binom{n}{i}\binom{m}{m-i}=\binom{m+n}{m}

暂时先从组合意义理解,注意边界

n=mn=m,有

i(ni)2=(2nn)\sum_{i}\binom{n}{i}^2=\binom{2n}{n}

三项式恒等式

(rm)(mk)=(rk)(rkmk)\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k}

平行求和法

0kn(r+kk)=(r+n+1n)\sum_{0\le k\le n}\binom{r+k}{k}=\binom{r+n+1}{n}

对杨辉三角手玩一下

上指标求和

0kn(km)=(n+1m+1)\sum_{0\le k\le n}\binom{k}{m}=\binom{n+1}{m+1}

对杨辉三角手玩一下

卡特兰数

0 1 2 3 4 5 6
1 1 2 5 14 42 132

关于卡特兰数的问题有两种不同的形式。

路线问题

使用这个问题构造双射比栈序列更容易理解

考虑一个网格图,你处于 (0,0)(0,0) 每次可以选择右走一格或者上走一格,且在任意的时刻,你往上走的次数不得超过往右走的次数,求走到 (n,n), n>0(n,n),\ n>0 的方案数。

考虑每个不合法的走路序列,其一定与直线 y=x+1y=x+1 有交点,假设某序列与直线 y=x+1y=x+1 的第一个交点为 P,那么将此直线在 PP 后的序列关于 y=x+1y=x+1 翻转,翻转后的序列结尾变为 (n1,n+1)(n-1,n+1),可以证明,从 (0,0)(0,0) 走到 (n1,n+1)(n-1,n+1) 的序列与上述的不合法序列构成双射,于是我们有方案数

Catn=(2nn)(2nn1)=(2nn)n+1Cat_n=\binom{2n}{n}-\binom{2n}{n-1}=\frac{\binom{2n}{n}}{n+1}

定义 CatnCat_n 为卡特兰数

与路线问题本质相同的问题有

  • 合法括号序列

  • 进出栈

  • 不相交弦

    圆周上有 2n2n 个互不相等的点,将它们两两连边,求弦互不相交的方案数。

    任取某一个点和一个方向(顺时针或逆时针),然后按方向扫描点,将某条弦第一次在此方向出现的端点作为左括号 ‘(’,第二次出现的端点作为右括号 ‘)’ ,可以发现所有不相交连边方案与合法括号序列构成双射。

二叉树问题

nn 个点无标号二叉树个数,考虑 dp,设 dpndp_ndp0=1dp_0=1) 表示答案,枚举跟节点和左右节点个数,则有

dpn=i=0n1dpi×dpni1dp_n=\sum_{i=0}^{n-1}dp_i\times dp_{n-i-1}

它的同构问题均可以使用 dp 解决

可以证明,dpndp_n 即为 CatnCat_n

生成函数练习 2

证明一哈

斯特林数

第二类斯特林数

定义 {nk}(S(n,k)){n\brace k} (S(n,k)) 表示 nn 个(不同的)元素,分给 kk 个(相同的)非空集合的方案数,我们有如下递推(分情况讨论即可)

{nk}={n1k1}+k{n1k1}{n0}=[n=0].\begin{aligned} &{n \brace k}={n-1 \brace k-1}+k{n-1 \brace k-1}\\ &{n \brace 0}=[n=0] \end{aligned}.

通项

{nk}=i=1k(1)kiini!(mi)!=1m!i=1k(1)kiin(mi)\begin{aligned} {n\brace k}&=\sum_{i=1}^k\frac{(-1)^{k-i}i^n}{i!(m-i)!}\\ &=\frac{1}{m!}\sum_{i=1}^k(-1)^{k-i}i^n\binom{m}{i} \end{aligned}

容斥练习2

留空为上式证明

生成函数练习3

留坑

第一类斯特林数

定义 [nk](s(n,k))\begin{bmatrix}n\\k\end{bmatrix}(s(n,k)) 表示 nn 个(不同的)元素,分给 kk 个(相同的)非空轮换的方案数,我们有如下递推(分情况讨论即可)

[nk]=[n1k1]+(n1)[n1k][n0]=[n=0]\begin{aligned} &\begin{bmatrix}n\\k \end{bmatrix}=\begin{bmatrix}n-1\\k-1 \end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k \end{bmatrix}\\ &\begin{bmatrix}n\\0 \end{bmatrix}=[n=0] \end{aligned}

  • 轮换:首位相接的环形排列,具有旋转等价性

  • 同大小排列与轮换构成双射

    排列与置换构成双射,置换可以分解为若干非空轮换

    k[nk]=n!\sum_k\begin{bmatrix}n\\k\end{bmatrix}=n!

幂与恒等式

xn=k[nk]xkxn=k{nk}xk\begin{aligned} &x^{\overline n}=\sum_k\begin{bmatrix}n\\k\end{bmatrix}x^k\\ &x^n=\sum_k{n\brace k}x^{\underline k}\\ \end{aligned}

上式均可采用归纳进行证明,可以对幂构造逆变换,首先我们有

xn=(1)n(x)nx^{\underline n}=(-1)^n(-x)^{\overline n}

将其带入上述公式,可以得到

xn=k[nk](1)nkxkxn=k{nk}(1)nkxk\begin{aligned} &x^{\underline n}=\sum_k\begin{bmatrix}n\\k\end{bmatrix}(-1)^{n-k}x^k\\ &x^n=\sum_k{n\brace k}(-1)^{n-k}x^{\overline k} \end{aligned}

尝试将原公式带入新产生的公式

xn=k{nk}(1)nkxk=k{nk}(1)nkm[km]xm=m(k[km]{nk}(1)nk)xm\begin{aligned} x^n&=\sum_k{n\brace k}(-1)^{n-k}x^{\overline k}\\ &=\sum_k{n\brace k}(-1)^{n-k}\sum_m\begin{bmatrix}k\\m\end{bmatrix}x^m\\ &=\sum_m(\sum_k\begin{bmatrix}k\\m\end{bmatrix}{n\brace k}(-1)^{n-k})x^m \end{aligned}

由于左右两边 xx 的系数需要相同,则有

k[km]{nk}(1)nk=[n=m]\sum_k\begin{bmatrix}k\\m\end{bmatrix}{n\brace k}(-1)^{n-k}=[n=m]

同理可以得到

k{km}[nk](1)nk=[n=m]\sum_k{k\brace m}\begin{bmatrix}n\\k\end{bmatrix}(-1)^{n-k}=[n=m]

称最后两个公式为反演系数

行与列

  • 第二类斯特林数行

    直接对通项卷积即可

  • 第二类斯特林数列

    留作生成函数练习4

  • 第一类斯特林数行

    利用倍增求 xnx^{\overline n} 的多项式表达,留作练习

  • 第一类斯特林数列

    留作生成函数练习5

斯特林反演

之后在反演大类里面应该会具体介绍,此处先简要说明

f(n)=k{nk}g(k)g(n)=k[nk](1)nkf(k)f(n)=k[nk]g(k)g(n)=k{nk}(1)nkf(k)f(n)=\sum_k{n\brace k}g(k)\Longleftrightarrow g(n)=\sum_{k}\begin{bmatrix}n\\k \end{bmatrix}(-1)^{n-k}f(k)\\ f(n)=\sum_k\begin{bmatrix}n\\k \end{bmatrix}g(k)\Longleftrightarrow g(n)=\sum_{k}{n\brace k}(-1)^{n-k}f(k)

以一式左推右为例(其余同理)

g(n)=ig(i)[i=n]=ig(i)k[nk]{ki}(1)nk=k(1)nk[nk]i{ki}g(i)=k(1)nk[nk]f(k)\begin{aligned} g(n)&=\sum_{i}g(i)[i=n]\\ &=\sum_ig(i)\sum_k\begin{bmatrix}n\\k\end{bmatrix}{k\brace i}(-1)^{n-k}\\ &=\sum_k(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}\sum_i{k\brace i}g(i)\\ &=\sum_k(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}f(k) \end{aligned}

贝尔数

0 1 2 3 4 5 6
1 1 2 5 15 52 203

称基数为 nn 的集合的划分方案的数目,记为 BnB_n

Bn+1=k(nk)BkB_{n+1}=\sum_k\binom{n}{k}B_k

这就是枚举新元素加入某个集合的 dp

由组合意义,我们有

Bn=k{nk}B_n=\sum_k{n\brace k}

生成函数练习6

比较有趣,留坑

伯努利数

先给出一些简单定义,后续在复习生成函数之后进行补充

0 1 2 3 4 5
11 12-\frac{1}{2} 16\frac{1}{6} 00 130-\frac{1}{30} 00

定义 Sm(n)=k=0n1kmS_m(n)=\sum\limits_{k=0}^{n-1}k^m,将其写成关于 nn 的多项式后,定义其系数为伯努利数,具体的,有

Sm(n)=1m+1(B0nm+1+(m+11)B1nm+(m+12)B2nm1++(m+1m)Bmn)=1m+1k=0m(m+1k)Bknm+1k\begin{aligned} S_m(n)&=\frac{1}{m+1}(B_0n^{m+1}+\binom{m+1}{1}B_1n^m+\binom{m+1}{2}B_2n^{m-1}+\dots+\binom{m+1}{m}B_mn)\\ &=\frac{1}{m+1}\sum_{k=0}^m\binom{m+1}{k}B_kn^{m+1-k} \end{aligned}

Sm(1)=[m=0]S_m(1)=[m=0]

k=0m(m+1k)Bk=[m=0]\sum_{k=0}^m\binom{m+1}{k}B_k=[m=0]

此式可以朴素求或构造生成函数

生成函数练习7

晚点

欧拉数

这,先留个坑吧

容斥

设全集 UU 中的元素可能有 nn 种不同的属性,其中(至少)拥有第 ii 种属性的元素构成集合 SiS_i,我们有

i=1nSi=iSii<jSiSj+i<j<kSiSjSk+(1)m1ai<ai+1Sa1Sa2Sam++(1)n1S1S2Sn\left|\bigcup_{i=1}^nS_i\right|=\sum_i|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\dots+(-1)^{m-1}\sum_{a_i<a_{i+1}}|S_{a_1}\cap S_{a_2}\cap\dots\cap S_{a_m}|+\dots+(-1)^{n-1}|S_1\cap S_2\cap \dots\cap S_n|

这个式子有一个广为人知的证明,即讨论每个元素被统计的次数,发现系数可以利用帕斯卡三角形同行奇偶项相等约到只剩系数 11

当具体问题为交集时,采用如下转化

Si=USi\left|\bigcap S_i\right|=|U|-\left|\bigcap\overline{S_i}\right|

一般化(子集反演)

设存在两个集合的函数 f(S),g(S)f(S),g(S),若有

f(S)=TSg(T)f(S)=\sum_{T\subseteq S}g(T)

那么有

g(S)=TS(1)STf(T)g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)

证明思路和普通的容斥原理相似,强行拆开后交换次序构造出奇偶项相等即可

其存在一个推论,在全集 UU 下,若有

f(S)=STg(T)f(S)=\sum_{S\subseteq T}g(T)

那么有

g(S)=ST(1)TSf(T)g(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}f(T)

例题

nn 个点有标号 DAG 的个数,n5000n\le5000 (此题有若干加强版,这里仅讨论运用子集反演的简单版,后续可能会在别的地方作为练习题补充)

在考虑 DAG 的连边情况时,入度或出度为 00 的点是特殊的,我们考虑以入度为 00 的点为基础进行统计,令 dpi,jdp_{i,j} 表示 ii 个点的 DAG,入度为 00 的点恰好为 jj 个的个数,我们有

dpi,j=(ij)k=1ij(2j1)k2(ijk)jfij,kdp_{i,j}={i\choose j}\sum_{k=1}^{i-j}(2^j-1)^k2^{(i-j-k)j}f_{i-j,k}

首先因为有标号,所以先钦定 jj 个点,然后枚举去掉这 jj 个点后的图中有多少个度为 00 的点(kk),这 kk 个点的每个点与 jj 个点的点集至少连一条有向边,然后 jj 个点的点集同时与剩下的 ijki-j-k 个点任意连边。

考虑对入度为 00 这个条件进行容斥,设 f(i,S)f(i,S) 表示 ii 个点的 DAG 中恰好集合 SS 的度数为 00g(i,S)g(i,S) 表示 ii 个点的 DAG 中至少集合 SS 的度数为 00,我们有

g(n,S)=STf(n,T)g(n,S)=\sum_{S\subseteq T}f(n,T)

由子集反演,则

f(n,S)=ST(1)TSg(n,T)f(n,S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}g(n,T)

我们的目标是 g(n,)g(n,\varnothing) ,那么有(U={1,2,,n}U=\{1,2,\dots,n\}

g(n,)=TUf(n,T)=TUTP(1)PTg(n,P)=TUTP(1)PTg(nP,)2P(nP)=PUg(nP,)2P(nP)TP(1)PT=k=1n(nk)g(nk,)2k(nk)i=1k(ki)(1)ki=k=1n(nk)g(nk,)2k(nk)([k=0](1)k)=k=1n(nk)g(nk,)2k(nk)(1)k1\begin{aligned} g(n,\varnothing)&=\sum_{\varnothing \not=T\subseteq U}f(n,T)\\ &=\sum_{\varnothing \not=T\subseteq U}\sum_{T\subseteq P}(-1)^{|P|-|T|}g(n,P)\\ &=\sum_{\varnothing \not=T\subseteq U}\sum_{T\subseteq P}(-1)^{|P|-|T|}g(n-|P|,\varnothing)2^{|P|(n-|P|)}\\ &=\sum_{\varnothing\not=P\subseteq U}g(n-|P|,\varnothing)2^{|P|(n-|P|)}\sum_{\varnothing\not=T\subseteq P}(-1)^{P-T}\\ &=\sum_{k=1}^n\binom{n}{k}g(n-k,\varnothing)2^{k(n-k)}\sum_{i=1}^k\binom{k}{i}(-1)^{k-i}\\ &=\sum_{k=1}^n\binom{n}{k}g(n-k,\varnothing)2^{k(n-k)}([k=0]-(-1)^k)\\ &=\sum_{k=1}^n\binom{n}{k}g(n-k,\varnothing)2^{k(n-k)}(-1)^{k-1} \end{aligned}

dp=g()dp=g(\varnothing) 即可朴素求出,为

dpn=i=1n(1)i1dpni(ni)2i(ni)dp_n=\sum_{i=1}^n(-1)^{i-1}dp_{n-i}\binom{n}{i}2^{i(n-i)}

上述推导过程相对麻烦,不妨感性认识一下这个转移式的容斥意义,我们枚举的 ii 即为钦定了度数为 00 的点,那么上式意义为 DAG 个数=至少一个点入度大于 00 的 DAG 个数 减去 至少两个点的入度大于 00 的 DAG 个数 加上 至少三个点的入度大于 00 的 DAG 个数 …

min-max容斥

  • 前置知识

    二项式反演

    f(n)=i=0n(ni)g(i)g(n)=i=0n(1)ni(ni)f(i)f(n)=\sum_{i=0}^n\binom{n}{i}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)

  • 一些定义

    max(S),min(S)\max (S),\min (S)表示分别集合SS的最大,最小元素

  • 套路式子

    max(S)=ST(1)T1min(T)\max(S)=\sum_{\varnothing\not=S\subseteq T}(-1)^{|T|-1}\min(T)

  • 证明

    首先我们先设一个容斥系数f(x)f(x)

    max(S)=STf(T)min(T)\max(S)=\sum_{\varnothing\not=S\subseteq T}f(|T|)\min(T)

    设集合SSnn个元素,我们讨论第kk小元素的贡献

    i=0nk(nki)f(i+1)=[nk=0]\sum_{i=0}^{n-k}\binom{n-k}{i}f(i+1)=[n-k=0]

    就是当这个元素成为最小值时另外再选几个比它要大的元素的方案,如果这个元素不是最大元素,要求不贡献

    F(n)=f(n+1),G(n)=[n=0]F(n)=f(n+1),G(n)=[n=0]

    上式为

    G(n)=i=0n(ni)F(i)G(n)=\sum_{i=0}^n\binom{n}{i}F(i)

    由二项式反演

    F(n)=i=0n(1)ni(ni)G(i)F(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}G(i)

    代回去

    f(n+1)=i=0n(1)ni(ni)[i=0]=(1)nf(n)=(1)n1\begin{aligned} f(n+1)&=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}[i=0]\\ &=(-1)^n\\ f(n)&=(-1)^{n-1} \end{aligned}

    所以有

    max(S)=ST(1)T1min(T)\max(S)=\sum_{\varnothing\not=S\subseteq T}(-1)^{|T|-1}\min(T)

  • 用处

    在期望意义下,这个式子依然成立,即

    E(max(S))=ST(1)T1E(min(T))E(\max(S))=\sum_{\varnothing\not=S\subseteq T}(-1)^{|T|-1}E(\min(T))

    下面给几个例题

  • 例题

    • HDU4336

      题意:有nn个卡牌,每秒有pip_i的概率抽到卡牌ii,求至少得到每个卡牌至少一张的期望时间

      min-max容斥有个套路思想就是化max为min,因为min一般比较好统计

      max(S)\max (S)表示集合SS中最后一个获得元素的期望时间,min(S)\min (S)代表集合SS中第一个获得元素的期望时间

      那么有上面的套路式子

      max(S)=ST(1)T1min(T)\max(S)=\sum_{\varnothing\not=S\subseteq T}(-1)^{|T|-1}\min(T)

      min(T)\min (T)就非常好求了

      min(T)=1iTpi\min(T)=\frac{1}{\sum_{i\in T}p_i}

      就是先把总概率算一下的事情

    • 「HAOI2015」按位或

      题意:初始有一个数00,每秒有pip_i的概率或(|)上整数i(i[0,2n))i(i\in [0,2^n)),求期望多少秒后数组变成2n12^n-1

      max(S)\max(S)表示最后一个或上去的期望时间,min(S)\min(S)同理

      式子随便套,考虑求出min(T)\min(T)

      min(T)=1STpS\min(T)=\frac{1}{\sum\limits_{S\cap T\not=\varnothing}p_S}

      考虑求底下的东西

      STpS=SUpSST=pS=SUpSST=SpS\begin{aligned} \sum_{S\cap T\not=\varnothing}p_S&=\sum_{S\subseteq U} p_S-\sum_{S\cap T=\varnothing}p_S\\ &=\sum_{S\subseteq U}p_S-\sum_{\overline S\cup T=\overline S}p_S \end{aligned}

      后面的东西取补集后是子集和的形式,我们可以FWTFWT或者FMTFMT2nn2^nn内求出

    • 「PKUWC2018」随机游走

      题意:树上随机游走,给定起点,每次询问至少走过一次点集的期望时间

      直接套路上去考虑如何求min(T)\min (T),即第一次到达给定点集的期望步数

      dpudp_u表示uu走到给定点集SS的期望步数,dud_uuu点度数

      uS,dpu=0u\in S,dp_u=0

      否则

      dpu=dpfadu+dpvdu+1=Audpfa+Bu\begin{aligned} dp_u&=\frac{dp_{fa}}{d_u}+\frac{\sum dp_v}{d_u}+1\\ &=A_udp_{fa}+B_u \end{aligned}

      就先把环状的转移和其他的分开搞一下,那么

      dpu=dpfadu+Avdpu+Bvdu+1dp_u=\frac{dp_{fa}}{d_u}+\frac{\sum A_vdp_u+B_v}{d_u}+1

      化简一下

      (1Avdu)dpu=dpfadu+Bvdu+1(1-\frac{\sum A_v}{d_u})dp_u=\frac{dp_{fa}}{d_u}+\frac{\sum B_v}{d_u}+1

      把左边除过去就可以了

      这样的话我们可以n2nlog998244353n2^n\log 998244353处理出每个集合的min(S)\min(S)了,仍然可以预处理子集和

  • kthmax-min容斥

    kthmax(S)=TS(1)Tk(T1k1)min(T)kthmax(S)=\sum_{\varnothing\not=T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)

    kthmax(S)kthmax(S)表示集合中第kk大的元素

    证明起来和普通的差不多

    设一个容斥系数f(n)f(n),统计nn个元素中第xx小的贡献

    i=0nx(nii)f(i+1)=[nx+1=k]i=0n(ni)f(i+1)=[n=k1]f(n+1)=i=0n(1)ni(ni)[i=k1]f(n)=(1)nk(n1k1)\sum_{i=0}^{n-x}\binom{n-i}{i}f(i+1)=[n-x+1=k]\\ \sum_{i=0}^n\binom{n}{i}f(i+1)=[n=k-1]\\ f(n+1)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}[i=k-1]\\ f(n)=(-1)^{n-k}\binom{n-1}{k-1}

  • 参考资料

    【Learning】min-max容斥以及推广kth min-max容斥

    min-max容斥

LGV 引理

一般用于求 DAG 上不相交路径的数量

  • 相关定义:

    pp ​表示图上某一个路径,Pu,vP_{u,v}​ 表示图上以 uu​ 为起点以 vv​ 为终点的路径集合

    ω(p)\omega(p)​​​ 表示路径 pp​​​ 上所有边权之积

    e(u,v)=pPu,vω(p)e(u,v)=\sum_{p\in P_{u,v}}\omega(p)​​

    定义超级起点集合 AA​,超级终点集合 BB​,且 A=B=n|A|=|B|=n​,σ(S)\sigma(S)​ 为一个 1n1\sim n​ 的排列,sign(σ(S))\mathtt{sign}(\sigma(S))​ 表示 σ(S)\sigma(S)​ 逆序对的奇偶性,即 (1)inversion number in σ(S)(-1)^{\mathbf{inversion \ number \ in \ \sigma(S)}}​​​

    一组( nn 条) ABA\rightarrow B 的路径 SSSiS_i 表示一条从 AiA_iBσ(S)iB_{\sigma(S)_i}​​ 的路径

    一组( nn 条) ABA\rightarrow B 的不相交路径 S0S_0SiS_i 表示一条从 AiA_iBσ(S)iB_{\sigma(S)_i} 的路径,其中路径两两没有交点

  • 引理

    M=[e(A1,B1)e(A1,B2)e(A1,Bn)e(A2,B1)e(A2,B2)e(A2,Bn)e(An,B1)e(An,B2)e(An,Bn)]det(M)=S:ABsign(σ(S))i=1nω(Si)=S0:ABsign(σ(S))i=1nω(Si)\begin{aligned}M&=\begin{bmatrix} e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n)\\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n)\\ \vdots&\vdots&\ddots&\vdots\\ e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n) \end{bmatrix}\\ \det(M)&=\sum_{S:A\rightarrow B}\mathtt{sign}(\sigma(S))\prod_{i=1}^n\omega(S_i)\\ &=\sum_{S_0:A\rightarrow B}\mathtt{sign}(\sigma(S))\prod_{i=1}^n\omega(S_i) \end{aligned}

    所有系数为正的相交序列和所有为负的相交序列可以按照第一个交点任意排列,构成的奇偶排列数量相等,构成双射

    而一般来说,只有正排列 (1,2,,n)(1,2,\dots,n) 构成的路径能做到没有交点,因此一般最后 det(M)\det(M)​ 求的就是整排列对应的无交路径

  • 例题

    二维网格图有 nn​​ 个起点 (0,a1),(0,a2),,(0,an)(0,a_1),(0,a_2),\dots,(0,a_n)​​ 和 nn​​ 个终点 (1,0),(2,0),,(n,0)(1,0),(2,0),\dots,(n,0)​​,每一步只能向右或向下走,询问有多少个从对应起点到对应终点不相交的路径组 1n5×105,0ai106,ai<ai+1,mod9982443531\le n \le 5\times10^5,0\le a_i\le 10^6,a_i< a_{i+1},\bmod 998244353​​​

    直接套用 LGV 引理即可,但是 nn 比较大,我们需要一些后续处理

    det(M)=[(a1+11)(a1+22)(a1+nn)(a2+11)(a2+22)(a2+nn)(an+11)(an+22)(an+nn)]=i=1n1i![(a1+1)1(a1+1)2(a1+1)n(a2+1)1(a2+1)2(a2+1)n(an+1)1(an+1)2(an+1)n]=i=1nai+1i![1(a1+1)1(a1+1)2(a1+1)n1(a2+1)1(a2+1)2(a2+1)n1(an+1)1(an+1)2(an+1)n]=i=1nai+1i!1i<jn(aiaj)\begin{aligned} \det(M)&=\begin{bmatrix} \binom{a_1+1}{1}&\binom{a_1+2}{2}&\cdots&\binom{a_1+n}{n}\\ \binom{a_2+1}{1}&\binom{a_2+2}{2}&\cdots&\binom{a_2+n}{n}\\ \vdots&\vdots&\ddots&\vdots\\ \binom{a_n+1}{1}&\binom{a_n+2}{2}&\cdots&\binom{a_n+n}{n}\\ \end{bmatrix}\\ &=\prod_{i=1}^n\frac{1}{i!}\begin{bmatrix} (a_1+1)^{\overline{1}}&(a_1+1)^{\overline{2}}&\cdots&(a_1+1)^{\overline{n}}\\ (a_2+1)^{\overline{1}}&(a_2+1)^{\overline{2}}&\cdots&(a_2+1)^{\overline{n}}\\ \vdots&\vdots&\ddots&\vdots\\ (a_n+1)^{\overline{1}}&(a_n+1)^{\overline{2}}&\cdots&(a_n+1)^{\overline{n}}\\ \end{bmatrix}\\ &=\prod_{i=1}^n\frac{a_i+1}{i!}\begin{bmatrix} 1&(a_1+1)^{1}&(a_1+1)^{2}&\cdots&(a_1+1)^{n}\\ 1&(a_2+1)^{1}&(a_2+1)^{2}&\cdots&(a_2+1)^{n}\\ \vdots&\vdots&\ddots&\vdots\\ 1&(a_n+1)^{1}&(a_n+1)^{2}&\cdots&(a_n+1)^{n}\\ \end{bmatrix}\\ &=\prod_{i=1}^n\frac{a_i+1}{i!}\prod_{1\le i<j\le n} (a_i-a_j) \end{aligned}

    第一步把每一列的 1i!\frac{1}{i!} 提取出来,第二步注意到 nn 次上升幂可以看作 nn 次多项式,这样后面项数大的可以不断减前面项数小的,把上升幂转成普通幂,最后再每一行提取一个 (ai+1)(a_i+1) ,第三步直接使用范德蒙行列式

    范德蒙德行列式:

    [1111x1x2x3xnx12x22x33xn2x1nx2nx3nxnn]=1i<jn(xixj)\begin{bmatrix} 1&1&1&\cdots&1\\ x_1&x_2&x_3&\cdots&x_n\\ x_1^2&x_2^2&x_3^3&\cdots&x_n^2\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ x_1^n&x_2^n&x_3^n&\cdots&x_n^n \end{bmatrix}=\prod_{1\le i<j\le n}(x_i-x_j)

    最后设 fai=1,gmxai=1f_{a_i}=1,g_{mx-a_i}=1 两个卷一下,取大于 mxmx 的系数,可以得到某个权值的出现次数,注意到 aia_i 互不相同,因此次数不超过 998244353,不需要使用任意模数,直接 NTT 即可


数论

约定

  • O(1) 快速乘

    1
    2
    3
    4
    5
    ll ksc(ll a,ll b,ll p)
    {
    ull c=(ull)a*b-(unsigned)((long double)a/p*b+0.5L)*p;
    return c<p?c:c+p;
    }

同余方程

裴蜀定理等

CRT及其扩展

BSGS

见邝斌板子

二次剩余

原根与高次剩余

筛法

万金油线筛

素数判定与整除

这两个东西比较万金油

Miller-Rabin

前置知识:

  1. 费马小定理

    ap11(modp),p is primea^{p-1}\equiv 1\pmod p,p \ is \ prime

  2. 二次探测( mod\bmod 奇素数下 11 的二次剩余 )

    x21(modp)x=1 or p1x^2\equiv 1\pmod p\Longrightarrow x=1 \ or \ p-1

    如果不是 mod\bmod 奇素数,二次剩余可能是更多的值

如果把费马小定理反过来用来检测一个数是否是素数,虽然是错的,但是反例比较少,如果配合二次探测进行测试并取多个 aa,可以把 110181\sim 10^{18} 内的所有数是否是质数判断出来。

具体的,取 aa 为前 1212 个质数 (2,3,5,7,11,13,17,19,23,29,31,37)(2,3,5,7,11,13,17,19,23,29,31,37)

然后用费马小定理进行测试,如果 ap11(modp)a^{p-1}\equiv 1\pmod p ,就根据二次探测检验是否有 a(p1)/21(modp)a^{(p-1)/2}\equiv 1\pmod p ,如果值为 11 ,就递归 (p1)/4(p-1)/4 处理,如果值为 p1p-1 或无法向下递归(指数为奇数)直接返回 true ,否则返回 false

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int pri[]={2,3,5,7,11,13,17,19,23,29,31,37};
bool ck(ll a,ll k,ll p)
{
ll x=qp(a,k,p);//a^k mod p
if(x!=1&&x!=p-1) return false;
if(x==p-1) return true;
if(k&1) return true;
return ck(a,k>>1,p);
}
bool Miller_Rabin(ll p)
{
if(p==1) return false;
for(int i=0;i<12;i++) if(p%pri[i]==0) return p==pri[i];
for(int i=0;i<12;i++)
if(!ck(pri[i],p-1,p))
return false;
return true;
}

这样做的复杂度是 12log2n12\log^2 n,其中因子的个数是一个log\log,里面每次还做了一次快速幂。

考虑从底向上做,就是说,先求出 x1x-122 到不能除的最底层的 xx ,这样每次向上一层直接就直接平方 x2x^2 即可

考虑在某一层 x=1x=1,那么如果之前的一层的 xp1x'\not=p-1 的话,就不合法了,或者在最上面一层 xx 仍然不为 11 ,也是不合法的

这样就优化掉了一个 log\log

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int pri[]={2,3,5,7,11,13,17,19,23,29,31,37};
bool Miller_Rabin(ll p)
{
if(p==1) return false;
for(int i=0;i<12;i++) if(p%pri[i]==0) return p==pri[i];
ll res=p-1;int k=0;
while(!(res&1)) res>>=1,++k;
for(int i=0;i<12;i++)
{
ll x=qp(pri[i],res,p);
for(int j=0;j<k&&x>1;j++)
{
ll y=ksc(x,x,p);
if(y==1&&x!=p-1) return false;
x=y;
}
if(x!=1) return false;
}
return true;
}

Pollard Rho

现在需要求出 nn 的最大约数,考虑在 [1,n1][1,n-1] 随便 rand 两个数 x,yx,y ,若 gcd(x+nymodn,n)1 or n\gcd(x+n-y\bmod n,n)\not=1 \ or \ n ,则 xy\left|x-y\right |nn 的一个约数

假设现在有一个近似的随机函数 ff

fm(x)=f(fm1(x))f_m(x)=f(f_{m-1}(x)) ,由于同余系的封闭性,则若干步后一定有循环出现,次数若还没找到约数就退出

具体的,初始 x=y=rand()x=y=rand(),每一步时 x=f(x)x=f(x)y=f(f(y))y=f(f(y)) ,如果 x=yx=y 第二次出现,那么说明存在环,可以证明,环最多被遍历一次就会被找到

f(x)=x2+cf(x)=x^2+ccc 是随机正整数

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ll f(x,c,p){return (ksc(x,x,p)+c)%p;}
ll Find(ll n)
{
for(int i=0;i<12;i++) if(n%pri[i]==0) return pri[i];
ll x=rand(),y=x,c=rand();
int lim=1e5;
do
{
ll g=gcd((x-y+n)%n,n);
if(g!=1&&g!=n) return g;
x=f(x,c,n),y=f(f(y,c,n),c,n);
}while(x!=y&&lim--);
return -1;
}
void Pollard_Rho(ll n,ll &a)
{
if(n<a) return;
while(!(n&1)) n>>=1;a=2;
if(n==1||Miller_Rabin(n)) {a=a>n?a:n;return;}
ll d=Find(n);
while(d==-1) d=Find(n);
if(d<n/d) d=n/d;
Pollard_Rho(d,a),Pollard_Rho(n/d,a);
}

这样做的复杂度是 O(n14logn)O(n^{\frac{1}{4}}\log n)

考虑将复杂度优化掉一个 w(127,512,)w(127,512,\dots)

注意到 gcd(x,n)gcd(xymodn,n)\gcd(x,n)|\gcd(xy\bmod n,n)

可以倍增 yy 的步数,在每次倍增中,ww 步取一次 gcd\gcd ,若其为 11,说明没找到,继续重复,若为 nn ,说明这一次倍增中得到答案,回去重新走一遍,中间遇到不为 11 的就返回,不过这样可能会得到 nn ,我们就在外面重跑

这样复杂度可以近似认为是 (n14)(n^\frac{1}{4})

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
ll f(x,c,p){return (ksc(x,x,p)+c)%p;}
ll Find(ll n)
{
for(int i=0;i<12;i++) if(n%pri[i]==0) return pri[i];
ll x,y=rand(),c=rand();
int w=1<<9;
for(int l=1;;l<<=1)
{
x=y;
for(int i=0;i<l;i++) y=f(y,c,n);
for(int i=0;i<l;i+=w)
{
int le=min(l-i,w);
ll g=1,las=y;
for(int j=0;j<le;j++) g=ksc(g,(y+n-x)%n,n),y=f(y,c,n);
g=gcd(g,n);
if(g==1) continue;
if(g==n)
{
y=las,g=1;
while(g==1) g=gcd((y+n-x)%n,n),y=f(y,c,n);
}
return g;
}
}
}
void Pollard_Rho(ll n,ll &a)
{
if(n<a) return;
while(!(n&1)) n>>=1;a=2;
if(n==1||Miller_Rabin(n)) {a=a>n?a:n;return;}
ll d=Find(n);
while(d==n) d=Find(n);
if(d<n/d) d=n/d;
Pollard_Rho(d,a),Pollard_Rho(n/d,a);
}

杜教筛

Min_25筛

Dirichlet 卷积

反演

二项式反演

莫比乌斯反演

斯特林反演

单位根反演


杂项

概率期望

博弈

群论

代数结构(S,)(S,\cdot)​​​ 有封闭,结合,单位元,逆元,称群

陪集

设群 GG 某一子群为 HHgG\forall g\in G,定义 HH 的某左陪集为 gH={ghhH}gH=\{gh|h\in H\}

引理1: a,bGa,b \in G​​,aHaH​​ 与 bHbH​​ 要么相等,要么不交

推论1(拉格朗日定理):G=H×D|G|=|H|\times|D|​​,DD​​ 为 HH​​​​ 不同的陪集个数

轨道-稳定子定理(orbit-stabilizer theorem)

定义1:置换群

置换:有限集合到自身的双射称为置换,定义在其上的乘法比较显然

置换群:定义在某个确定集合 XX 的全部置换与其乘法构成置换群

定义2:轨道 (orbit)

xX\forall x \in X​​​​ ,轨道 Ox={g(x)gG}O_x=\{g(x)|g\in G\}​​​​,又记为 xGx^G​​​​,GG​​​​ 为 XX​​​​ 的置换群

因为群的可逆性,所以 OxO_x