0x37 容斥原理与莫比乌斯函数
滑稽的小宫
·
·
个人记录
容斥原理
包含原理
设 S_1,S_2,S_3,\cdots,S_n 为有限集合，|S| 表示集合 S 的大小，则：
|\bigcup \limits_{i=1}^n S_i|=\sum\limits_{i=1}^n|S_i|-\sum\limits_{i=1,j=1,i<j}^n |S_i\cap S_j|+\sum\limits_{i=1,j=1,k=1,i<j<k}^n|S_{i}\cap S_j\cap S_k|-\cdots+(-1)^{n+1}|S_1\cap S_2\cap\cdots\cap S_n|
=\sum_{k=1}^n(-1)^{k+1}\biggl (\sum\limits_{1\leq i_1<i_2<\cdots<i_k\leq n} |\bigcap\limits_{j=1}^kS_{i_j}|\biggr)
翻译成人话就是：一些有限集合的并集的元素个数，等于所有集合的元素个数之和，减去任意两个集合交集的元素个数之和，加上任意三个集合交集的元素个数之和，以此类推
证明： 考虑一个属于左侧并集的元素 a ，假设 a\in S_{i_1},S_{i_2},S_{i_3},\cdots,S_{i_k},(k\in[1,n],i_j\in[1,n]) 这几个集合，且不属于其他集合，那么在上式左端a产生了一次贡献，在上式右端，第一个求和中a产生了 C_{k}^1 次贡献，第二个求和中a产生了 C_{k}^2 次贡献（任意两个集合之交都会恰好统计一次，而k个包含a的集合产生的两集合之交一共是k个集合中选两个的方案数），以此类推。
最终a对右侧的贡献为
\sum_{i=1}^n(-1)^{i-1}C_k^i
=C_k^0-\sum_{i=0}^n(-1)^iC_k^i
根据二项式定理，(x+1)^k=\sum_{i=0}^nC_k^i x^i，可得：
=C_k^0-(-1+1)^k=1
对于每个存在于所有集合并集的元素，其对两边的贡献都是1，对于不存在于任意集合中的元素，对两边的贡献都是0，因此最终两边相等。
证毕.
应用
包含原理主要运用于多种情况分类讨论，最后合并为一个大集合时的计数原理
逐步淘汰原理（筛法公式）——排除原理
定理：设 S 为问题全集，A_i\subset S，则：
|\bigcap_{i=1}^n \complement_SA_i|=|S|-\sum_{1\leq i\leq n}|A_i|+\sum_{1\leq i<j\leq n}|A_i\cap A_j|-\cdots+(-1)^n|A_1\cap _2\cap \cdots\cap A_n|
=|S|-|\bigcup_{i=1}^n A_i|
翻译成人话，就是从全集中不断减去一些集合，一个元素重复的减去只算作一次，那么最后剩下的元素数量，就等于全集减去这些集合并起来的元素数量（这是很显然的）
证明： 根据上面的语言叙述，我们不难想到，每个集合的补集的交就相当于这些集合的并的补集。这实际上是德·摩根定律的集合论形式，即 \complement_U(A\cup B)=\complement_UA\cap \complement_UB
因此 |\bigcap_{i=1}^n \complement_SA_i|=|\complement_S(\bigcup_{i=1}^nA_i)|=|S|-|\bigcup_{i=1}^n A_i|
应用
这个公式相对于包含原理有更广泛的运用，主要用于正着求不好求的时候，可以求不满足给定条件的数量（从任意转化为存在），然后得到给定条件1的方案数量，再用排除原理算出去掉这些不满足条件2的情况的数量。
上述两种原理称为包含与排除原理
例1：伯努利装错信笺问题
有n个不同的信和n个不同的信封，第i封信与第i个信封对应，每个信封放且只放一封信，求不存在一封装对的信的情况下，放信的方案数。
解： 将一种放法定义为集合的一个元素，那么不考虑没有信装对这一个条件，放法总数就是 A_n^n=n!，其全集对应为 S
然后我们利用逐步淘汰原理，从这个全集中去掉有一个信放对的，加上有两个信放对的，去掉有三个信放对的，以此类推，假设有一个信i放对的集合为 A_{i}，则：
|A_i|=(n-1)!,|A_i\cap A_j|=(n-2)!,|A_i\cap A_j\cap A_k|=(n-3)!,\cdots
|S|-C_n^1(n-1)!+C_n^2(n-2)!-\cdots+(-1)^nC_n^n
=n!(1-\frac{1}{1!}+\frac{1}{2!}-\cdots+(-1)^n\frac{1}{n!})
这个问题又叫做乱序排列问题，即将n个元素排列打乱，使每个元素都不在原来的位置上的排列数
置换及不动点
给定集合 X=\{1,2,3,\cdots,n\}，设 \varphi 是从 X 到 X 上的双射，记为：
1&2&\cdots&n\\\varphi(1)&\varphi(2)&\cdots&\varphi(n)
\end{matrix}\right\}
则称 \varphi 是 X 上的置换，其中 \varphi(i) 是元素 i 在映射 \varphi 下的象。因为是一一对应，所以 \varphi(1),\varphi(2),\cdots,\varphi(n) 是一个n个全排列。
满足 \varphi(i)=i 的 i 称为 \varphi 的一个不动点。
根据上例，集合 X=\{1,2,\cdots,n\} 上没有任何不动点的置换个数为：
D_n=n!\sum_{i=0}^n\frac{(-1)^i}{i!}
例2
设 \varphi 是集合 X=\{1,2,\cdots,n\} 上的置换，将 X 上没有不动点的置换个数记为 f_n，恰有一个不动点的置换个数记为 g_n ，证明：|f_n-g_n|=1
证明： 设 g_{n_i} 表示恰有一个不动点 i 的方案数，则有 g_n=\sum_{i=1}^n g_{n_i}
由于恰有一个不动点，就相当于剩下n-1个点都不是不动点，因此 g_{n_i}=D_{n-1}，所以 g_n=nD_{n-1}，所以：
|f_n-g_n|=|D_n-nD_{n-1}|
=|n!\sum_{i=0}^n\frac{(-1)^i}{i!}-n\cdot (n-1)!\sum_{i=0}^{n-1}\frac{(-1)^i}{i!}|
=|n!\cdot \frac{(-1)^n}{n!}|=1
证毕.
多重集的组合数
设 S 是由 n_1 个 a_1，n_2 个 a_2，直到 n_k 个 a_k 组成的多重集，一共有 n 个元素，则对于任意整数 m\leq n，从S中取出m个组成的多重集的数量为：
C_{k+m-1}^{k-1}-\sum_{i=1}^n C_{k+m-n_i-2}^{k-1}+\sum_{1\leq i<j\leq k}C_{k+m-n_i-n_j-3}^{k-1}-\cdots +(-1)^kC_{k+m-\sum_{i=1}^k n_i-k-1}
证明： 首先假设没有每个元素取用个数限制，则根据可重复的组合原理，组合个数为 C_{k+m-1}^{k-1}
考虑构造集合 S_i 为第i种元素至少选了 n_i+1 个的情况，那么我们可以先选出 n_i+1 个 a_i，然后无限制地选剩下的，方案为 C_{k+(m-n_i-1)-1}^{k-1}，这就是 |S_i|
然后对于 |S_i\cap S_j|，即是第i种和第j种元素都至少有 n_i+1 和 n_j+1 个，那么方案数就是先选出 n_i+1 个 a_i，再选出 n_j+1 个 a_j，最后再无限制地选剩下的，方案为 C_{k+(m-n_i-1-n_j-1)-1}^{k-1}
以此类推，再根据筛法公式，就得到了上式
证毕.
注意： 如果组合数中选出的数大于原有元素个数，那么暂时认为其方案数为0.
莫比乌斯函数
除了从狄利克雷卷积的角度考虑单位元的逆元为莫比乌斯函数，还可以从容斥原理角度考虑。
首先列出莫比乌斯函数的解析式：
若 n=\prod_{i=1}^kp^{c_i}_i
\mu(n)=
\begin{cases}
0 &\exists c_i>1\\
(-1)^k &else
\end{cases}
然后考虑莫比乌斯反演里面的一个经典问题：求 \sum_{i=1}^a\sum_{j=1}^b[\gcd(a,b)=k]
首先按反演的思路处理：(除法均向下取整)
=\sum_{i=1}^{a/k}\sum_{j=1}^{b/k}[\gcd(i,j)=1]
然后我们有一个结论：
=\sum_{i=1}^{\min(a,b)}\mu(i)\sum_{x=1}^a\sum_{y=1}^b[i|\gcd(x,y)]
这个结论可以用容斥证明，设D(a,b,k)=\sum_{x=1}^a\sum_{y=1}^b[k|\gcd(x,y)]，求出小于a/k和b/k的互质的数对个数，可以用全部的数对 D(a,b,1)=a*b，减去gcd是某一个质数倍数的数对个数 D(a,b,2),D(a,b,3)\cdots，加上gcd是某两个不同质数乘积倍数的数对个数 D(a,b,6),D(a,b,10),\cdots，减去gcd是某三个质数乘积倍数的数对个数……以此类推。
发现莫比乌斯函数中，奇数个本质不同质因子项为减，偶数个为加，某一个质因子多于一个则为0，因此就是这个容斥的结构，直接放到 D(a,b,i) 的前面作为系数即可。
因此总共的式子就是 \sum_{i=1}^{min(a,b)}\mu(i)D(a,b,i)
而 D(a,b,i)=\sum_{x=1}^a\sum_{y=1}^b[k|\gcd(x,y)]=\sum_{x=1}^a\sum_{y=1}^b[k|x][k|y]
=\sum_{x=1}^a[k|x]\sum_{y=1}^b[k|y]=\lfloor a/k\rfloor\lfloor b/k\rfloor
因此总的式子就是 \sum_{i=1}^{\min(a,b)}\mu(i)\lfloor a/i\rfloor\lfloor b/i\rfloor ，莫比乌斯函数用线性筛，D函数用二维整除分块计算即可
复杂度为 O(a+T\sqrt a)（设a大于b）