容斥原理
Meteor_
·
·
个人记录
容斥原理
引入
先来举一个例子：
求 1000 以内能够被 2 或 3 或 5 整除的数的个数
分别去求能被 2/3/5 整除的数个数是比较简单的。那我们可以设 A 代表能够被 2 整除的数的集合，B 代表能够被 3 整除的数的集合，C 代表能够被 5 整除的数的集合。那么我们所要求答案就是 |A \cup B \cup C|
简单一想，就知道这个答案并不等同于 |A| + |B| + |C|，原因就是这里面有不少重复计算的值。
我们接下来观察一张图：
从图中可得，虽然我们将一些值重复计算了 2 次甚至是 3 次，但是我们可以通过求交集的方式来得到它们，然后就能轻松的得到答案，所以我们有了下面这个式子：
|A \cup B \cup C| &= (|A| + |B| + |C|) - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|
\end{aligned}
容斥原理
我们观察上面那个式子，虽然有加有减，但是不难发现加和减是交替出现的，所以我们可以通过特殊情况下的式子推出普遍适用的式子：
|\bigcup_{i = 1}^n S_i &= \sum_{1 \le i \le n}|S_i| - \sum_{1 \le i < j \le n}|S_i \cap S_j| + \dots + (-1)^{n - 1}|S_1 \cup S_2 \cup \dots \cup S_{n - 1} \cup S_n| \\
&= \sum_{i = 1}^n (-1)^i \sum
\end{aligned}
未完待续......