「OI之路」03数学-8反演与容斥

反演与容斥

计数的核心技能

容斥

基础的是统计全集,当年werkeytom举了个dwjshift夺WC-CTSC-APIO三金的故事

我比较喜欢用二项式反演不带脑子地推:$f恰g至,\sum_{i=1}^n f_i=\sum_{i=1}^n \sum_{j=i}^n (-1)^{j-i}C_j^ig_j=\sum_{j=1}^n g_j*(\sum_{t=0}^{j-1} C_j^t(-1)^t=(-1)^{j+1})$


广义容斥先不讲了,大概就是二项式反演,见经典题bzoj4665已经没有什么好害怕的了HAOI2018 染色

一道可以做的题:玲珑学院1138 震惊,99%+的中国人都会算错的问题
$$
ans=\sum_{集合S} f(|S|) \lfloor \frac{n}{lcm(S)} \rfloor,
其中f为容斥系数,我们希望\sum_{i=1}^n C_n^if_i=n\%2 \\
这里f可以n^2递推求,但其实是可以计算的 \\
二项式反演,f_n=\sum_{i=1}^n(-1)^{n-i}C_n^i[i\%2=0],经典技巧之 \frac{x^i+(-x)^i}{2}
\\
[n=0]-\frac{ [n=0]+\sum_{i=1}^i C_n^i (-1)^{n-i} (-1)^i }{2}=(-2)^{n-1}
$$


带权容斥:有的时候你需要对带权值的东西容斥,题如CEOI2019游乐园uoj193「UR#14」人类补完计划

一个经典的系数是$A^{|S|}$,以容斥至少为例,即枚举了集合T,因为不知道|S|,那么我们的系数只能跟|T|相关,设为$pp(|T|)$

那么一个实际集合为S的方案,会被$T \subseteq S$的所有T统计一次,$A^{|S|}=\sum_{T \subseteq S} pp(|T|)$,而二项式定理告诉我们,$A^{|S|}=\sum_{T \subseteq S} (A-1)^{|T|}$,那么令$pp(i)=(A-1)^i$即可

以前曾经自己手推过,有点小长,想看的请展开

当时一个方案的系数为$(y^{-1})^{|S|}$,f为恰好g为至少
$$
\\ g_i=\sum_{j=i} C_j^if_j,(G_i=g_iy^{-i})=\sum_{j=i} C_j^i y^{j-i}(F_j=f_jy^{-j}),设容斥系数z,F_i=\sum_{j=i} z(i,j)G_j
\\ F_i=\sum_{j=i} z(i,j) \sum_{k=j} C_k^j y^{k-j}F_k=\sum_{k=i} F_k \sum_{j=i}^k z(i,j)C_k^jy^{k-j},那么要找到z使得\sum_{j=i}^k z(i,j)C_k^jy^{k-j}=[k-i=0]
\\ 这里本来都想直接找规律了,但发现并不难推,先把右边化成(某些k-i相关且=1)*\sum_{t=0}^{k-i} C_{k-i}^t (-1)^t,思考怎么把左边搞成那样
\\ 很自然想起经典的C_k^jC_j^i=C_{k}^iC_{k-i}^{j-i},非常自然地想到z(i,j)=C_j^i(-1)^{j-i}y^{j-i}
\\ 验证一下,上面那个就是\sum_{j=i}^k C_j^i(-1)^{j-i}y^{j-i}C_k^jy^{k-j}=(y^{k-i}C_k^i)*[k-i=0],没毛病
\\ ans=\sum F_i=\sum_i\sum_{j=i} g_jy^{-j}C_j^i(-1)^{j-i}y^{j-i}=\sum_j g_j (Y=y^{-1}-1 )^j,于是计算j的时候一个方案的权就是Y^j
$$

题单:

理论上都写了题解,已剔除上面的例题

  1. AGC005 D - ~K Perm Counting
  2. 各种图计数,都挺不错的,见「快乐计数」
  3. 「ZJOI2016」小星星
  4. ARC093F Dark Horse

反演

对初学者,强烈推荐vfk的ppt,特别详细

因为我比较懒,如果下面式子省略太多没看懂,可以同步看cjfdf

框架

$$
f(n)=\sum_k a_{n,k}g(k),g(n)=\sum_k b_{n,k}f(k),已知b求a \\
f(n)=\sum_k a_{n,k} \sum_m b_{k,m}f(m)=\sum_m f(m) \sum_k a_{n,k}b_{k,m},即\sum_k a_{n,k}b_{k,m}=[n=m] \\
$$

写成$N*N$的矩阵的形式,已知$f=A*g,g=B*f$,则$f=A*B*f$,$A*B=I,B=A^{-1}$

于是本质就是找到b的逆矩阵a,用于反演

二项式反演

先敲下黑板:$[n=m]=\sum_k a_{n,k}b_{k,m}$

  1. 已知$f_i = \sum_{j=0}^N {i \choose j} g_j$,即下三角

$$
[n=m]=[n-m=0]{n\choose m}
=\sum_k {n\choose m} {n-m \choose k}(-1)^k
=\sum_k {n\choose m+k} {m+k \choose m}(-1)^k
=\sum_k {n\choose k} {k \choose m}(-1)^{k-m}
$$

由$a_{n,k}={n \choose k}$,我们直接能写出$b_{k,m}={k \choose m}(-1)^{k-m}$,因此有$g_i=\sum_{j=0}^N (-1)^{i-j} {i \choose j} f_j$

  1. 已知$f_i = \sum_{j=0}^N {j \choose i} g_j$,即上三角

$$
[n=m]=[m-n=0]{m\choose n}
=\sum_k {m\choose n} {m-n \choose k} (-1)^k
=\sum_k {m\choose n} {m-n \choose m-k} (-1)^{m-k}
\\
=\sum_k {m\choose n} {m-n \choose k-n} (-1)^{m-k}
=\sum_k {m\choose k} {k \choose n} (-1)^{m-k}
$$

由$a_{n,k}={k \choose n}$,我们直接能写出$b_{k,m}={m \choose k}(-1)^{m-k}$,因此有$g_i=\sum_{j=0}^n (-1)^{j-i} {j \choose i} f_j$

集合反演

这就是IFMT的原理

  1. 已知 $f(S)=\sum_{T\subseteq S}g(T)$

$$
g(S)
=\sum_{T\subseteq S} [S \setminus T=0] g(T)
=\sum_{T\subseteq S} \sum_{Q\subseteq S \setminus T} (-1)^{|Q|}g(T)
=\sum_{Q\subseteq S} (-1)^{|Q|} \sum_{T\subseteq S \setminus Q} g(T)
=\sum_{Q\subseteq S} (-1)^{|Q|} f(S-Q)
=\sum_{T\subseteq S} (-1)^{|S \setminus T|} f(T)
$$

  1. 已知 $f(S)=\sum_{S\subseteq T}g(T)$

$$
g(S)
=\sum_{S\subseteq T} [T-S=0] g(T)
=\sum_{S\subseteq T} \sum_{Q\subseteq T-S} (-1)^{|Q|} g(T)
=\sum_{S\subseteq Q} (-1)^{|Q|-|S|} \sum_{Q\subseteq T} g(T)
=\sum_{S\subseteq Q} (-1)^{|Q|-|S|} f(Q)
$$

所以其实二项式反演只是这个的特殊情况

莫比乌斯反演

先介绍下莫比乌斯函数:

对于普通集合的容斥,我们一般使用组合数

而处理多重集合时,我们需要定义新的数

而比较常见的多重集合是质因子分解式

我们定义莫比乌斯函数$\mu(x)=无平方因子^{不同质因子个数}$,有些常用式子:

  1. $[n=1]=\sum_{d|n} \mu(d)$,简洁写法是$e=I \ast \mu$(狄利克雷卷积,详见积性函数一章)
    证明:只关心n的质因子集合而与次幂无关,设集合大小为k,则就是$\sum_{i=0}^k C_k^i (-1)^i=[k=0]$
  2. $\sum_{d|n} \frac{\mu(d)}{d}=\frac{\varphi(n)}{n}$
    证明:把n移动到左边,就是容斥求phi的方法(枚举gcd的质因子集合的子集,做个简单容斥)

就像有了组合数就方便做普通容斥了一样,有了莫比乌斯函数我们将方便地对质因子这个多重集做容斥

其实就是集合反演,所以好像也没必要证明啥了……

先敲下黑板:$[n=m]=\sum_k a_{n,k}b_{k,m}$

  1. 已知$f_i = \sum_{j=0}^n [j|i] g_j$,即下三角矩阵

根据 $[n=1]=\sum_{d|n} \mu(d)$,我们知道$[n=m]=\sum_{d|\frac{n}{m}} \mu(d)=\sum_{T} [T|n][m|T] \mu(\frac{T}{m})$

$a_{n,T}=[T|n]$,我们直接能写出$b_{T,m}=[m|T] \mu( \frac{T}{m} )$,因此有$g_i=\sum_{j=0}^n [j|i]\mu(\frac{i}{j}) f_j$

  1. 已知$f_i = \sum_{j=0}^n [i|j] g_j$,即上三角矩阵

反过来用不就完事了吗?$[n=m]=\sum_{d|\frac{m}{n}} \mu(d)=\sum_{T}[n|T] [T|m] \mu(\frac{m}{T})$

$a_{n,T}=[n|T]$,我们直接能写出$b_{T,m}=[T|m] \mu( \frac{m}{T} )$,因此有$g_i=\sum_{j=0}^n [i|j]\mu(\frac{j}{i}) f_j$

莫反入门题表(前面没啥好看的)-popoqqq

进阶题表

  1. 「WC2014」时空穿梭

  2. 百度之星2019初赛R3C 算术 ,一道不是很难的莫反题,但却教我做人

    主要是考虑到i和j是等价的,不应该把D给某一方,而是$\mu(ijD)=[gcd(i,j)=1]\mu(iD)\mu(jD)\mu(D)$

  3. UR#5 怎样跑得更快

$$
\sum_{j=1}^n f(gcd(i,j)) \cdot g(i) \cdot h(j) \cdot x_j=b_i \\
考虑f(n)=\sum_{d|n}f_r(d),实际意义是什么并不重要,反演就能求 \\
\sum_{j=1}^n \sum_{d=1}^n [d|i][d|j] f_r(d) \cdot h(j) \cdot x_j=b_i/g(i) \\
\sum_{d=1}^n [d|i]f_r(d)[ \sum_{d|j} h(j) \cdot x_j]=b_i/g(i) \\
\sum_{d|i} f_r(d) gg(d)=gg2(i),gg2、f_r都已知,可以反演得到gg \\
gg(d)=\sum_{d|j} h(j)x_j ,反演得右边即可
$$

这就是传说中的“三次反演掷地有声——vfk”,code

斯特林反演

$g_k=\sum_{i=k}^n S_2(i,k) f_i \leftrightarrow f_k=\sum_{i=k}^n(-1)^{i-k} S_1(i,k) g_i$

证明

例题:异或图Square(那场模拟赛的C)

单位根反演

前置

复数域:高中数学内容

欧拉公式:$e^{xi}=cos(x)+sin(x) i$

n次单位根:对于方程$w^n=1$,如果我们能找到n个不同的解,则称他们为n个n次单位根($w_{n}^o,w_n^1..w_n^{n-1}$,其中$w_n^i=(w_n^1)^i$)

对于复数域,可以构造$\omega_n^k = e^{ 2 \pi \frac{k}{n} i }$;对于模意义数域,如果$n|(MOD-1)$且存在原根g,可以构造$w=g^ \frac{MOD-1}{n}$

单位根反演

$[n\%d=0]=\frac{1}{d} \sum_{k=0}^{d-1} \omega_d^{nk}$

证明考虑左边成立时右边就是1,左边不成立时$w_{d}^{nk} \ne1$,等比数列求和得到$\frac{1}{d}*\frac{(w_d^{n})^k-1}{(w_d^{n})-1}=0$

这个东西配合生成函数的理论很好用

另外对于d=2蛮常见的,可以不看做是单位根反演
$$
现在有一个函数 f(x)=\sum_{i=0}^N a_ix^i,求g(x)=\sum_{i=0}^n a_i[i\%d=0] \\
= \sum_{i=0}^n a_i \frac{1}{d}\sum_{k=0}^{d-1}\omega_{d}^{ik}
= \frac{1}{d} \sum_{k=0}^{d-1} \sum_{i=0}^n a_i(\omega_{d}^k)^i
= \frac{1}{d} \sum_{k=0}^{d-1} f(w_d^k) \\
$$
这样就可以计算某些f点值很好算而要求算倍数项系数的题目了,比较常见的是二项式定理求点值


loj6485 LJJ 学二项式定理,code
$$
\begin{aligned}
f(x)&=\sum_{i=0}^nC_n^iS^ix^i=S^n(S^{-1}+x)^n \\
ans&=\frac{1}{4} \sum_{r=0}^3 a_r \sum_{k=0}^3 \omega_4^{-rk}f(\omega_4^k) \\
\end{aligned}
$$
bzoj3328 PYXFIB,记得模数不定要自己求原根来着……code
$$
fib用矩乘A^i算,然后A和I都是正方形,二项式定理同样适用\\
f(x)=\sum_{i=0}^n C_n^i A^i*I^{n-i} \ x^i=(Ax+I)^n\\
ans=\frac{1}{k}\sum_{i=0}^{k-1} f(\omega_k^i)
$$
uoj450「集训队作业2018」复读机

min-max容斥(最值反演)

(2019.8 重写了一遍)

注意下面的大小关系都是可以我们自己定义的,并不一定是数字的大小,比较常见的应用是期望

假定容斥系数只跟集合的大小有关,然后假设我们现在求的是第k小
$$
枚举非空子集T,kth(S)=\sum_{T \subseteq S} A(|T|) min(T),考虑第n小元素的系数 \\
{[n=k]}=\sum_{i=0}^{|S|-n} C_{|S|-n}^i A(i+1),考虑化成二项式反演的形式 \\
C(x)=[|S|-x=k]=\sum_{i=0}^x C_x^i (B(i)=A(i+1)) ) \\
B(x)=\sum_{i=0}^x (-1)^{x-i}C_x^i [|S|-i=k]=(-1)^{x-(|S|-k)}C_x^{|S|-k} \\
kth(S)=\sum_{T \subseteq S} (-1)^{(|T|-1)-(|S|-k)} C_{|T|-1}^{|S|-k} min(T) \\
特例:max(S)=\sum_{T \subseteq S} (-1)^{(|T|-1)} min(T)
$$
HAOI2015 按位或luogu4707 重返现世

UNR1 合唱队形PKUWC2018 随机游走

这个也可以推到gcd和lcm中,就是对每个质因子考虑其次数,得$lcm(S)=\prod_{T \subseteq S} gcd(T)^{(-1)^{|T|}-1}$

例题bzoj4833 [Lydsy1704月赛]最小公倍佩尔数 (需要掌握fib的那几条性质,见定理杂烩)
$$
枚举非空子集T,g(n)=\prod_{D=1}^n (P_D)^{ f(D)=\sum_T [gcd=D] (-1)^{|T|+1} }\\
f(D)=\sum_d \mu(d)\sum_{d|num}^{n/D}\sum\sum … (-1)^{|T|+1},mx=\lfloor \frac{n}{dD} \rfloor \\
考虑二项式定理,f(D)=\sum_d \mu(d)(-\sum_{t=1}^{mx} C_{mx}^t (-1)^t) \\
=\sum_d \mu(d)(-(mx^0-1))=-\sum_d \mu(d)[dD \le n] \\
g(n)=\prod_{D=1}^n (P_D)^{ sum\mu(n/D) } \\
考虑到\lfloor (n-1)/D \rfloor \ne \lfloor n/D \rfloor 当且仅当 D|n
$$

故预处理好mu及其逆元,nlogn预处理每个数的约数,逐个求出g即可,$O(nlogn)$,由于使用vc,bzoj过不去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vc<int> dd[N];int P[N],invP[N];
void main()
{
pre();for(int i=1;i<N;i++) for(int j=i;j<N;j+=i) dd[j].PB(i);
P[1]=invP[1]=1;
int T=qread();
while(T--)
{
int n=qread();MOD=qread();
int ans=1;
for(int i=2,gg=1;i<=n;i++)
{
if(i>1) P[i]=((ll)P[i-1]+P[i-1]+P[i-2])%MOD,invP[i]=invm(P[i]);
for(int t=0;t<(int)dd[i].size();t++)
{
int D=dd[i][t];
if(mu[i/D]==1) gg=(ll)gg*P[D]%MOD;
else if(mu[i/D]==-1) gg=(ll)gg*invP[D]%MOD;
}
ans=(ans+(ll)gg*i)%MOD;
}
write2(ans);
}
}

51nod1355 斐波那契的最小公倍数 ,比这题更简单

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/3b5e.html
转载请注明出处,谢谢!