容斥 反演 学习笔记

数学，数论

---

---

参考：
https://blog.csdn.net/werkeytom_ftd/article/details/74701513
https://www.luogu.org/blog/KingSann/chu-tan-rong-chi-yuan-li
https://ac.nowcoder.com/discuss/184169?type=101&order=0&pos=10&page=1

这里只是简单整理一下，方便复习。

---

最基本的容斥

有$n$种属性，若干个物品，每个物品可能有这$n$种属性的若干种。假设我们可以容易地计算出$f(S)$表示属性中至少包含$S$集合的物品个数。求至少有$1$种属性的物品个数。（就是最经典的模型，有三科语数英，已知语数英各有多少人满分，语数、数英、语英分别有多少人同时满分，有多少人三科都满分，求至少有一科满分的人有多少）
不知道为什么反正我们知道，答案是$\sum_{s\in S}(-1)^{|s|+1}f(s)$（$s$为所有科目的子集，$f(s)$为$s$中所有科目都满分的人数）。
考虑它为什么是对的。对于一个有$n$种属性的物品，当$n=0$时，显然不会被计算。我们需要证明，$n>0$时，它会被恰好计算一次。
不难发现在枚举$i$种属性（大小为$i$的$s$）时，它会被计算$C_n^i$次。所以它被统计的次数$=\sum_{i=1}^nC_n^i(-1)^{i+1}=1$（把一个$-1$提出来，补一个$C_n^0$，二项式定理一下）。

更一般的容斥

有$n$种属性，若干物品。假设我们可以容易地计算出，$g(S)$表示属性包含$S$集合的物品个数。且给定$w(k)$表示，当物品拥有$k$个属性时它的价值是多少。求所有物品的价值和。
我们需要确定一个容斥系数$f(k)$，使得$Ans=\sum_{s\in S}g(s)f(|s|)$。
同上，考虑令每个物品被算入的贡献等于我们想要的数。即对于一个拥有$k$种属性的物品，需要满足

$$\sum_{i=1}^kC_k^if(i)=w(k)$$

$f(i)$是可以递推的。假设已知$f(1)...f(k-1)$，

$$\sum_{i=1}^kC_k^if(i)=w(k)\ \Rightarrow\ f(k)=w(k)-\sum_{i=1}^{k-1}C_k^if(i)$$

复杂度是$O(n^2)$的。
把阶乘展开发现大概能写成一个卷积形式，可以多项式求逆做到$O(n\log n)$。也可以反演去推。（见上面链接）
当然大部分题中是用$O(n^2)$/手推来找规律算的。

例题：“玲珑杯” 线上赛 Round#17 B。
$Description$
给定$m$个数$A_i$和$n$。求$1\sim n$中有多少个数能被奇数个$A_i$整除。
$T\leq 1000$组数据，$n\leq10^5,\ m\leq15$。

$Solution$
至少整除某个$A_i$集合的数有多少个很好算，所以考虑容斥。设容斥系数是$f(i)$，答案是$\sum_{s\in S}f(|s|)\lfloor\frac{n}{lcm(s)}\rfloor$。
对于被$k$个数整除的数，有$\sum_{i=1}^kC_k^if(i)=k\ \text{mod}\ 2$。可以$O(m^2)$递推或者打表得出$f(i)$（当然有规律是$f(i)=(-2)^{i-1}\ (i\neq0)$）。然后就做完啦。

---

下面只是一些要背的式子

二项式反演

$$f(n)=\sum_{i=0}^nC_n^ig(i)\ \Leftrightarrow\ g(n)=\sum_{i=0}^n(-1)^{n-i}C_n^if(i)$$

例题：[BZOJ]。

斯特林反演

$$f(n)=\sum_{i=0}^n{n\brace i}g(i)\ \Leftrightarrow\ g(n)=\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}f(i)$$

例题：[BZOJ4671]异或图，雅礼集训18.1.16 方阵。

莫比乌斯反演

$$F(d)=\sum_{d\mid n}f(d)\ \Leftrightarrow\ f(d)=\sum_{d\mid n}\mu(\frac nd)F(n)\\F(n)=\sum_{d\mid n}f(d)\ \Leftrightarrow\ f(n)=\sum_{d\mid n}\mu(\frac nd)F(d)$$