容斥原理

引入

是 个吗？不是的，因为有些学生可能同时喜欢数学和语文，或者语文和编程，甚至还有可能三者都喜欢。

为了叙述方便，我们把喜欢语文、数学、编程的学生集合分别用 表示，则学生总数等于 。刚才已经讲过，如果把这三个集合的元素个数 直接加起来，会有一些元素重复统计了，因此需要扣掉 ，但这样一来，又有一小部分多扣了，需要加回来，即 。即

把上述问题推广到一般情况，就是我们熟知的容斥原理。

定义

设 U 中元素有 n 种不同的属性，而第 i 种属性称为 ，拥有属性 的元素构成集合 ，那么

即

证明

对于每个元素使用二项式定理计算其出现的次数。对于元素 x，假设它出现在 的集合中，那么它的出现次数为

于是每个元素出现的次数为 1，那么合并起来就是并集。证毕。

补集

对于全集 U 下的 集合的并 可以使用容斥原理计算，而集合的交则用全集减去 补集的并集 求得：

右边使用容斥即可。

可能接触过容斥的读者都清楚上述内容，而更关心的是容斥的应用

那么接下来我们给出 3 个层次不同的例题来为大家展示容斥原理的应用。

不定方程非负整数解计数

没有限制时

如果没有 的限制，那么不定方程 的非负整数解的数目为 .

略证：插板法。

相当于你有 个球要分给 个盒子，允许某个盒子是空的。这个问题不能直接用组合数解决。

于是我们再加入 个球，于是问题就变成了在一个长度为 的球序列中选择 个球，然后这个 个球把这个序列隔成了 份，恰好可以一一对应放到 个盒子中。那么在 个球中选择 个球的方案数就是 。

容斥模型

接着我们尝试抽象出容斥原理的模型：

1. 全集 U：不定方程 的非负整数解
2. 元素：变量 .
3. 属性： 的属性即 满足的条件，即 的条件

目标：所有变量满足对应属性时集合的大小，即 .

这个东西可以用 求解。 可以用组合数计算，后半部分自然使用容斥原理展开。

那么问题变成，对于一些 的交集求大小。考虑 的含义，表示 的解的数目。而交集表示同时满足这些条件。因此这个交集对应的不定方程中，有些变量有 下界限制，而有些则没有限制。

能否消除这些下界限制呢？既然要求的是非负整数解，而有些变量的下界又大于 ，那么我们直接 把这个下界减掉，就可以使得这些变量的下界变成 ，即没有下界啦。因此对于

的不定方程形式为

于是这个也可以组合数计算啦。这个长度为 的 数组相当于在枚举子集。

HAOI2008 硬币购物

如果用背包做的话复杂度是 ，无法承受。这道题最明显的特点就是硬币一共只有四种。抽象模型，其实就是让我们求方程 的非负整数解的个数。

采用同样的容斥方式， 的属性为 . 套用容斥原理的公式，最后我们要求解

也就是无限背包问题。这个问题可以预处理，算上询问，总复杂度 。

完全图子图染色问题

前面的三道题都是容斥原理的正向运用，这道题则需要用到容斥原理逆向分析。

数学形式

一看这道题的算法趋向并不明显，因此对于棘手的题目首先抽象出数学形式。得分差即为奇偶对称差，可以用 -1 的幂次来作为系数。我们求的是

容斥模型

相邻结点染同一种颜色，我们把它当作属性。在这里我们先不遵守染色的规则，假定我们用 m 种颜色直接对图染色。对于图 ，我们把它当作 元素。属性 的含义是结点 i,j 染同色（注意，并未要求 i,j 之间有连边）。

而属性 对应的 集合 定义为 ，其含义是所有满足该属性的图 的染色方案，集合的大小就是满足该属性的染色方案数，集合内的元素相当于所有满足该属性的图 的染色图。

回到题目，“相邻的结点必须染同一种颜色”，可以理解为若干个 集合的交集。因此可以写出

上述式子右边的含义就是说对于 S 内的每一条边 都满足 的染色方案数，也就是 .

是不是很有容斥的味道了？由于容斥原理本身没有二元组的形式，因此我们把 所有 的边 映射到 个整数上，假设将 映射为 ，同时 映射为 . 那么属性 则定义为 .

同时 S 可以表示为若干个 k 组成的集合，即 .（也就是说我们在边集与数集间建立了等价关系）。

而 E 对应集合 . 于是乎

逆向分析

那么要求的式子展开

于是就出现了容斥原理的展开形式，因此对这个式子逆向推导

再考虑等式右边的含义，只要满足 任一条件即可，也就是存在两个点同色（不一定相邻）的染色方案数！而我们知道染色方案的全集是 ，显然 . 而转化为补集，就是求两两异色的染色方案数，即 . 因此

解决这道题，我们首先抽象出题目数学形式，然后从题目中信息量最大的条件， 函数的定义入手，将其转化为集合的交并补。然后将式子转化为容斥原理的形式，并 逆向推导 出最终的结果。这道题体现的正是容斥原理的逆用。

数论中的容斥

使用容斥原理能够巧妙地求解一些数论问题。

容斥原理求最大公约数为 k 的数对个数

考虑下面的问题：

这道题固然可以用欧拉函数或莫比乌斯反演的方法来做，但是都不如用容斥原理来的简单。

由容斥原理可以得知，先找到所有以 为 公约数 的数对，再从中剔除所有以 的倍数为 公约数 的数对，余下的数对就是以 为 最大公约数 的数对。即 以 为 公约数 的数对个数 以 的倍数为 公约数 的数对个数。

进一步可发现，以 的倍数为 公约数 的数对个数等于所有以 的倍数为 最大公约数 的数对个数之和。于是，可以写出如下表达式：

由于当 时，我们可以直接算出 ，因此我们可以倒过来，从 算到 就可以了。于是，我们使用容斥原理完成了本题。

上述方法的时间复杂度为 。

附赠三倍经验供大家练手。

• Luogu P2398 GCD SUM
• Luogu P2158[SDOI2008]仪仗队
• Luogu P1447[NOI2010]能量采集

容斥原理推导欧拉函数

考虑下面的问题：

直接计算是 的，用线性筛是 的，杜教筛是 的（话说一道数论入门题用容斥做为什么还要扯到杜教筛上），接下来考虑用容斥推出欧拉函数的公式

判断两个数是否互质，首先分解质因数

那么就要求对于任意 ， 都不是 的倍数，即 . 把它当作属性，对应的集合为 ，因此有

全集大小 ，而 表示的是 构成的集合，显然 ，并由此推出

因此可得

这就是欧拉函数的数学表示啦

容斥原理一般化

容斥原理常用于集合的计数问题，而对于两个集合的函数 ，若

那么就有

证明

接下来我们简单证明一下。我们从等式的右边开始推：

我们发现后半部分的求和与 无关，因此把后半部分的 剔除：

记关于集合 的函数 ，并化简这个函数：

因此原来的式子的值是

分析发现，仅当 时有 ，这时 ，对答案的贡献就是 ，其他时侯 ，则对答案无贡献。于是得到

综上所述，得证。

推论

该形式还有这样一个推论。在全集 下，对于函数 ，如果

那么

这个推论其实就是补集形式，证法类似。

DAG 计数

直接 DP

考虑 DP，定义 表示 个点的 DAG，有 点个入度为 的图的个数。假设去掉这 个点后，有 个点入度为 ，那么在去掉前这 个点至少与这 个点中的某几个有连边，即 种情况；而这 个点除了与 个点连边，还可以与剩下的点任意连边，有 种情况。因此方程如下：

计算上式的复杂度是 的。

放宽限制

上述 DP 的定义是恰好 个点入度为 , 太过于严格，可以放宽为至少 个点入度为 。直接定义 表示 个点的 DAG 个数。可以直接容斥。考虑选出的 个点，这 个点可以和剩下的 个点有任意的连边，即 种情况：

计算上式的复杂度是 的。

Min-max 容斥

对于满足全序关系并且其中元素满足可加减性的序列 ，设其长度为 ，并设 ，则有：

证明： 考虑做一个到一般容斥原理的映射。对于 ，假设 是第 大的元素。那么我们定义一个映射 。显然这是一个双射。

那么容易发现，对于 ，，。因此我们得到：

然后再把 映射回 ，而 是类似的。

证毕

但是你可能觉得这个式子非常蠢，最大值明明可以直接求。之所以 min-max 容斥这么重要，是因为它在期望上也是成立的，即：

证明： 我们考虑计算期望的一种方法：

其中 是一个长度为 的序列。

我们对后面的 使用之前的式子：

调换求和顺序：

是类似的。

证毕

还有更强的：

规定若 ，则 。

证明： 不妨设 。则有：

又因为有组合恒等式：，所以有：

当 时：

否则：

所以：

剩下三个是类似的。

证毕

根据 min-max 容斥，我们还可以得到下面的式子：

因为 分别相当于 ，就是说相当于对于指数做了一个 min-max 容斥，自然就是对的了

PKUWC2018 随机游走

期望游走的步数也就是游走的时间。那么设随机变量 表示第一次走到结点 的时间。那么我们要求的就是

使用 min-max 容斥可以得到

对于一个集合 ，考虑求出 。

考虑 的含义，是第一次走到 中某一个点的期望时间。不妨设 表示从结点 出发，第一次走到 中某个结点的期望时间。

• 对于 ，有 。
• 对于 ，有 。

如果直接高斯消元，复杂度 。那么我们对每个 都计算 的总复杂度就是 ，不能接受。我们使用树上消元的技巧。

不妨设根结点是 ，结点 的父亲是 。对于叶子结点 ， 只会和 的父亲有关（也可能 ，那样更好）。因此我们可以把 表示成 的形式，其中 可以快速计算。

对于非叶结点 ，考虑它的儿子序列 。由于 。因此可以得到

那么变换一下可以得到

于是我们把 也写成了 的形式。这样可以一直倒推到根结点。而根结点没有父亲。也就是说

解一下这个方程我们就得到了 ，再从上往下推一次就得到了每个点的 。那么 。时间复杂度 。

这样，我们可以对于每一个 计算出 ，时间复杂度 。

回到容斥的部分，我们知道 。

不妨设 ，那么进一步得到 。因此可以使用 FMT（也叫子集前缀和，或者 FWT 或变换）在 的时间内对每个 计算出 ，这样就可以 回答询问了。

参考文献

王迪《容斥原理》，2013 年信息学奥林匹克中国国家队候选队员论文集

Cyhlnj《有标号的 DAG 计数系列问题》

Wikipedia - 全序关系