Part 0 容斥原理
§ 0.0 容斥原理及其本质
最常见到的容斥原理的形式如下：
如何理解？
假如说我们面对一个特殊的问题，计算某些集合的交集十分容易，也就是说，我们可以在极低的开销下，指定若干个属性，并统计拥有这些属性的元素的个数。
注意，不是“恰好拥有”，而就是简单的“拥有”。
现在我们定义一种操作，指定一个 \(k\)，对于所有大小为 \(k\) 的，由属性组成的集合，分别查询拥有这个集合内全部属性的元素个数，然后把所有结果相加。
注意！这里查询的不是并集，有一些元素会被计算多次！一些博客文章会把这种操作称为“查询至少有 \(k\) 个属性的元素数目”，这种称呼其实不是很严谨。
为了下面的叙述方便，我们把这一操作称为 “钦定拥有 \(k\) 个属性的元素数目”，这也是 OI 界对这种形式的操作的通常称呼。
那在这种条件下，如何统计一共有几个元素至少有一种属性呢？
我们统计钦定拥有 \(1\) 个属性的元素数目，显然所有由两个或者以上的属性的元素会被算重恰好两次。
接下来，只要我们参与运算的量都是形如【钦定拥有 \(>1\) 种属性的元素数目】，那么那些只有一个属性的元素就不会受到影响了，他们就已经彻底被解决了。
那么我们减去钦定拥有 \(2\) 个属性的元素的数目，但是这样似乎又会减多了，虽然拥有两个属性的东西的数目都正确了，但是拥有更多属性的都降到零了。
所以为了填补这部分的空缺，继续重复以上过程直到结束，就得到了最上面的式子。
一般来说，容斥原理适用于以下的两种情况：
- 计数满足多个条件其一的对象数目。把满足一个条件的对象组成一个集合，然后直接套用容斥即可。
- 计数满足所有条件的对象数目。这个时候把限制取反，那么计数的对象转变为求所有满足至少一条限制的对象数目，这个可以用容斥做，再用全集的大小减去这个答案。
经验：做容斥题的时候，想办法让“限制的数目”变成一个常量，方法包括但不限于加入大小为零的对象、不可能满足的条件等。
事实上，容斥原理的表达式还蕴含了一个信息：每个元素对于右侧式子的贡献为 \(1\)，对左侧式子的贡献也为 \(1\) .
换句话说，如果每个元素的权值不一样的情况下，对于任意的函数 \(f(x)\) 而言，也有如下形式的容斥原理：
\[\sum_{x}\left(\left[ x\in \bigcup_{i=1}^{n} S_{i}\right]f(x)\right) = \sum_{i=1}^{n} (-1)^{i-1} \sum_{T\subseteq[1,n],|T|=i }\left(\sum_{x}\left[ x\in \bigcap_{j\in T} S_j \right]f(x)\right) \]
有点反人类
用另一种方法来写的话，我们考虑到表达式右侧的部分，相当于在 \(x\) 的限制集合中，挑选出一些，并根据挑选出的多少决定 \(x\) 向总和中贡献 \(1\) 还是 \(-1\) 次，也就是下面的式子：
很自然的，我们想把 \(T=\emptyset\) 的情况包括进去。
也就是
这个恒等式就是容斥原理的本质了，它对于任意的集合 \(S\) 都成立。
证明的话，用二项式系数就可以了。