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

容斥原理

描述

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

$${\displaystyle \begin{array}{rl}\left|\bigcup _{i=1}^n{A}_i\right|=& \sum _{i=1}^n|A_i|-\sum _{1\le i<j\le n}|A_i\cap A_j|+\sum _{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|-\cdots +(-1{)}^{n-1}|A_1\cap \cdots \cap A_n|.\end{array}}$$

其中 $\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$ 对应 $\stackrel{n\mathrm{位}}{\overbrace{0\dots 0010}}$，选 $A_1,A_3$ 对应 $\stackrel{n\mathrm{位}}{\overbrace{0\dots 0101}}$. 那么我们从 $1$ 遍历到 $2^n-1$ 即可将（除不选的）所有选择情况全部遍历到。如果可以全不选的话，从 $0$ 开始遍历。

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

$$\begin{array}{rl}i& =0001001001000011\\ i\gg 6& =0000000001001001\\ 1& =0000000000000001\\ i\gg 6\mathrm{\&}1& =0000000000000001\end{array}$$

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

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