容斥原理

当交集比并集更好计算时，可以通过容斥原理来转化：

$|A ∪B| = |A| + |B| − |A ∩B|$

$|A ∪B∪C| = |A| + |B| + |C| − |A ∩B| − |A ∩C| − |B∩C| + |A ∩B∩C|$

更一般的形式：
<img src="https://img2020.cnblogs.com/blog/1928767/202010/1928767-20201004175553721-1673457750.png" style="zoom: 50%;" />
证明：考虑集合中每个元素对等式两边的贡献。

对上式两侧取补集，并运用德摩根律，整理得
<img src="https://img2020.cnblogs.com/blog/1928767/202010/1928767-20201004175706938-821634117.png" style="zoom:50%;" />
则得到容斥原理的另一种形式，通常用于求同时满足多种限制条件时的
方案数，转化为计算同时不满足部分条件的方案数。