容斥的原理，代码实现，常见应用。

容斥原理及其应用

容斥原理

有一个集合$S$，有$P_1,P_2,...P_m$共$m$个性质，$S$中具有性质$P_i$的元素构成集合$A_i$，则：

$|\bar{A_1}\bigcap\bar{A_2}\bigcap...\bar{A_m} | = |S| - \sum|A_i|+\sum|A_i\bigcap A_j|-\sum|A_i\bigcap A_j\bigcap A_k| + ... + (-1)^m|A_1\bigcap...A_m|$

这就是容斥原理。

容斥原理的证明思路是：

• 对任意$x\in \bar{A_1}\bigcap\bar{A_2}\bigcap...\bar{A_m}$，证明$x$对等式左右两边的贡献都是$1$
• 对任意$x\notin \bar{A_1}\bigcap\bar{A_2}\bigcap...\bar{A_m}$且$x\in S$，证明$x$对等式左右两边的贡献都是$0$

由容斥原理很容易得到一个推论：

集合$S$中至少具有性质$P_1,P_2,...P_m$之一的对象的个数为：

$|A_1\bigcup A_2\bigcup...A_m | = \sum |A_i| - \sum|A_i \bigcap A_j| +... +(-1)^{m - 1}|A_1\bigcap A_2 \bigcap... A_m|$

式子可以由德摩根律轻松推出。

使用动机

容斥原理的使用经常出于以下两种动机：

• 从反面思考问题容易思考计数的策略。

• 从反面方便批量进行计数，比正面直接计算时间复杂度低。常见的情形是计数时发现计数结果只和选择的集合个数有关，与到底选了哪几个集合无关。这个时候有：

  $|\bar{A_1}\bigcap\bar{A_2}\bigcap...\bar{A_m} | = \sum_{i = 0}^m(-1)^i\tbinom{m}{i}\alpha_i$

  其中，$\alpha_i$代表选择$i$个集合的时候产生的贡献。容易发现这个式子的计算是$O(n)$的。而一般的容斥在计算的时候由于需要枚举子集，所以计算量至少是$O(2 ^n)$的。

应用举例

下面介绍一些容斥原理的应用，既包含比较偏组合数学课程的应用，也包含偏算法竞赛的应用。

普通集合上的应用

• 求$1$到$1000$中不能被$5,6$或$8$整除的数的个数：

  利用除法分别算出来能被$5,6,8$整除的数的个数，然后计算能被两两组合的最小公倍数整除的数的个数，最后计算能被三个数的最小公倍数整除的数的个数，容斥一下即可得到答案。

• 求$0$到$99999$中有多少同时含有$2,5,8$的整数：

  可以按照上一题的思路统计，也可以注意到不含有$1$个数的时候，不管是不含有$2,5,8$中的哪一个，贡献都一样多，所以可以较为简单的计数。

• 确定$S=\{1, 2,…, 8\}$的排列中没有偶数在它的自然位置上的排列数：

  同样可以发现可以按照有$1,2,3,4$个偶数在其自然位置上进行计数，然后容斥计算结果。

• 确定$S=\{1, 2,…, 8\}$的排列中至少有一个奇数在它的自然位置上的排列数：

  可以考虑四个性质分别是$1,3,5,7$在其自然位置上，则最终计数的就是$|A_1\bigcup A_2...\bigcup A_4|$，容斥原理推论即可。

多重集上的应用

基础知识：$k$种元素，每种元素可以取无限个，从这$k$种元素中取恰好$n$个元素，求方案数可以使用隔板法，结果是$\tbinom{n + k - 1}{k - 1}$ 。

利用容斥原理进行拓展：

• 确定多重集$T=\{3.a, 4.b, 5.c\}$的$10$子集的个数：

  可以看到并非每种元素可以随便选择。但是，我们仍然可以基于任意选择的方法利用容斥进行计数。考虑集合$S = \{\infin a, \infin b, \infin c\}$，$A_1$表示从$S$中拿出的包含不少于$4$个$a$的集合的集合，$A_2$表示从$S$中拿出的包含不少于$5$个$b$的集合的集合，$A_3$表示从$S$中拿出的包含不少于$6$个$c$的集合的集合。若对$S$做容斥，去掉这些个情况的方案，那么得到的就是$T$中取$10$子集的方案数，即$|\bar{A_1}\bigcap \bar{A_2}\bigcap \bar{A_3}|$ 。

• 不定方程整数解的个数，每个变量有一定的范围限制：

  做变量变换，把所有变量都调整成$x_i \geq 0$，然后就转化成了上一个问题。

错位排列

枚举有多少个数在它原来的位置，使用容斥原理，有：

$D_n = n! - \tbinom{n}{1}(n - 1)! + \tbinom{n}{2}(n - 2)! - \tbinom{n}{3}(n - 3)! + ... + (-1)^n\tbinom{n}{n}0!\\$

把组合数算出来，化简一下：

$D_n = n!(1 - \frac{1}{1!} + \frac{1}{2!} + ... + (-1)^n\frac{1}{n!})$

这就是错位排列数的计算公式了。

也可以通过递推的方式计算错位排列数$D_n$：

• 把数$1$放到其他位置上，然后把该位置原来的数放到$1$原来的位置上（即把$1$原来的位置当作被占用的那个位置原来的数的新的“原位”），有$(n - 1)D_{n - 2}$种方案。
• 把数$1$放到其他位置上，然后不把该位置原来的数放到$1$原来的位置上，有$(n - 1)D_{n - 1}$种方案。

所以，$D_n = (n - 1)(D_{n - 1} + D_{n - 2})$，$D_1 = 0, D_2 = 1$ 。

带有禁止位置的排列

没有什么很套路的计算方法，甚至可能使用容斥原理会使计算更加复杂。

带有绝对禁止位置的排列计数问题，在集合之间没有明显规律的时候，使用容斥原理统计可能会比较复杂，使用程序实现容斥原理也很可能是指数级的计算复杂度。

带有

$A_i$：第$i + 1$个人前面的人是上一次的人

几何问题