容斥原理:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。

容斥原理

描述

若 $A_1,\dots,A_n$ 为有限集,则

$$ {\displaystyle {\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|={}&\sum _{i=1}^{n}|A_{i}|-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|+\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}} $$

其中 $\left|A\right|$ 表示 $A$ 的基数。

举例

我们用图片举例分析,我们要求 $|A\cup B\cup C|$,可以先求 $|A|+|B|+|C|$,发现有三个重复部分,那就再减去 $|A\cap B|,|B\cap C|,|A\cap C|$,发现减多了一个部分,那就再补回去一个 $|A\cap B\cap C|$

(图片和公式来源:维基百科,使用 CC BY-SA 3.0 协议)

代码实现

在容斥原理中,我们枚举了 $A_1,\dots,A_n$ 的所有选择情况,一共 $2^n$ 种情况。我们可以使用 DFS 进行遍历,但通常我们使用二进制的方法进行遍历会更方便。

我们可以将每种选择情况对应到一个 $n$ 位的二进制数上,例如:选 $A_2$ 对应 $\overbrace{0\dots0010}^{n位}$,选 $A_1,A_3$ 对应 $\overbrace{0\dots0101}^{n位}$. 那么我们从 $1$ 遍历到 $2^n-1$ 即可将(除不选的)所有选择情况全部遍历到。如果可以全不选的话,从 $0$ 开始遍历。

那么我们怎么得知某一位是否为 $1$ 呢?使用位运算,i >> n & 1 如果为 $1$ 那么就说明 $i$ 的第 $n$ 位为 $1$. 例如:

$$ \begin{align} i &=0001\ 0010\ 0100\ 0011\\ i\gg6 &=0000\ 0000\ 0100\ 1001\\ 1 &=0000\ 0000\ 0000\ 0001\\ i\gg6\ \&\ 1&=0000\ 0000\ 0000\ 0001\\ \end{align} $$

for (int i = 1; i < (1 << n); i++)
    for (int j = 0; j < n; j++)
        if (i >> j & 1)
            ...

实际应用中,往往需要按题目调整位运算的方式,但总体思路仍然是使用二进制数来遍历。