容斥原理

计数最基础的东西。 首先我们要知道什么是计数。 集合 $A$ 的计数用 $|A|$ 表示，计数的严格表示就是：

$$|A|=\sum_{a\in A}1$$

其实就是集合 $A$ 中的元素个数。

容斥原理就是它的字面意思，容表示加，斥表示减，所以容斥原理就是加加减减。我们都学过，如果两个没有交集的集合 $A$ 和 $B$ 取并集的计数就是直接讲两个集合的计数相加，也就是 $|A \cup B|=|A|+|B|,A\cap B=\varnothing$，这个称为加法原理。同样的 $|A\times B|=|A|\times |B|$，这个被称为乘法原理。

我们可以注意到，在刚刚的加法原理中，有一个条件是 $A\cap B=\varnothing$，当时如果 $A\cap B\ne \varnothing$ 呢？这个时候就要用容斥原理了。

一般来说，求集合的交集比就集合的并集简单，所以容斥原理就是把并集转为交集。 最经典的就是有两个圆，他们有重叠部分，知道两个圆的面积和重叠面积，求总面积。这个问题的答案显然是把连个面积加起来，再把重叠面积相减。用集合来表示的话，就是

$$|A\cup B|=|A|+|B|-|A\cap B|$$

同样也通用于刚刚的加法原理。 类似的，三个集合的并集就是把每个面积加起来，再把每两个集的交集减去，这是发现中间的三个集合的交集减多了，所以要加回去。表示为：

$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|A\cap C|+|A\cap B\cap C|$$

容斥原理其实就是把这个式子推广到一般情况。

设有 $n$ 个集合，第 $i$ 个集合叫做 $A_i$，则：

$$\left|\bigcup^n_{i=1}A_i\right|=\sum_{\varnothing=I\subseteq \{1,2,\cdot\cdot\cdot,n\}}(-1)^{|I|+1}\left|\bigcap_{i\in I}A_i\right|$$

其中容和斥的部分分别是：

$$容：(-1)^{|I|+1}=1\to |I|\in\{1,3,5,7,\cdot\cdot\cdot\}$$ $$斥：(-1)^{|I|+1}=-1\to |I|\in\{2,4,6,8,\cdot\cdot\cdot\}$$

但是偶尔会出现求并集比求交集难容易的情况。 这是就要用到容斥原理的交集转并集。 设有 $n$ 个集合，第 $i$ 个集合叫做 $A_i$，$U$ 表示总集，则：

$$\bigcap^n_{i=1}A_i=\overline{\bigcup^n_{i=1}\overline{A_i}}\to\left|\bigcap^n_{i=1}A_i\right|=|U|-\left|\bigcup^n_{i=1}\overline{A_i}\right|\\ \left|\bigcup^n_{i=1}\overline{A_i}\right|=\sum_{\varnothing\ne I\subseteq \{1,2,\cdot\cdot\cdot,n\}}(-1)^{|I|+1}\left|\bigcap_{i\in I}\overline{A_i}\right|\\ \to\left|\bigcap^{n}_{i=1}A_i\right|=|U|-\sum_{\varnothing\ne I\subseteq \{1,2,\cdot\cdot\cdot,n\}}(-1)^{|I|+1}\left|\bigcap_{i\in I}\overline{A_i}\right|$$