容斥 反演 学习笔记
Tags: 数学，数论
参考：
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_{sin 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_{sin 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(nlog n))。也可以反演去推。（见上面链接）
当然大部分题中是用(O(n^2))/手推来找规律算的。
例题：“玲珑杯” 线上赛 Round#17 B 当咸鱼也要按照基本法，4.27模拟赛 A。
下面是第一道例题：
(Description)
给定(m)个数(A_i)和(n)。求(1sim n)中有多少个数能被奇数个(A_i)整除。
(Tleq 1000)组数据，(nleq10^5, mleq15)。
(Solution)
至少整除某个(A_i)集合的数有多少个很好算，所以考虑容斥。设容斥系数是(f(i))，答案是(sum_{sin S}f(|s|)lfloorfrac{n}{lcm(s)}
floor)。
对于被(k)个数整除的数，有(sum_{i=1}^kC_k^if(i)=k ext{mod} 2)。可以(O(m^2))递推或者打表得出(f(i))（当然有规律是(f(i)=(-2)^{i-1} (i
eq0))）。然后就做完啦。
下面只是一些要背的式子
二项式反演
例题：[BZOJ3622]已经没有什么好害怕的了。
PS：已经不知道哪年能补上题目了。
斯特林反演
例题：[BZOJ4671]异或图，雅礼集训18.1.16 方阵。