容斥原理
容斥原理
假设有全集U，以及全集的若干子集A1,A2,…,Ak。
在实际应用中要统计多个子集的交集的大小是比较容易的，但是要统计多个子集的并集的大小则比较困难。对于这种情况，我们可以使用容斥原理将并运算简化为若干次交运算。
记K表示由1,2,…,k组成的集合。容斥原理的公式如下：
|A1∪A2∪…∪Ak|=−∑I⊆K∧I≠∅(−1)|I||⋂i∈IAi|以及
|¯A1∪A2∪…∪Ak|=|S|−|A1∪A2∪…∪Ak|=∑I⊆K(−1)|I||⋂i∈IAi|广义容斥原理
给定全集U，以及全集的若干子集A1,A2,…,Ak。
容斥原理求的是U中有多少元素被至少一个子集Ai所包含。而广义容斥求的是被正好m个子集所包含的元素数目。
记α(m)=∑I⊆K∧|I|=m|⋂i∈IAi|。记β(m)表示被正好m个子集包含的元素数目，那么有：
β(m)=|U|∑i=m(−1)i−m(im)α(i)证明如下：
考虑任意一个元素e∈U，设e在t个子集中出现。考虑三种情况：
- t<m，那么t在等式的左右贡献都是0。
- t=m，那么t在等式的左右贡献恰好都是1。
- t>m，那么t在等式的左右贡献都是0。
其中t>m的情况详细说明一下右边为什么是0。很显然t在α(i)中贡献为(ti)。因此对右边的贡献为：
t∑i=m(−1)i−m(im)(ti)=t∑i=m(−1)i−m(tm)(t−mi−m)=(tm)t−m∑i=0(−1)i(t−mi)=(tm)(1−1)t−m=0提供一道题目：
min-max容斥
max{S}=∑T⊆S(−1)|T|+1min{T}min{S}=∑T⊆S(−1)|T|+1max{T}证明：
考虑第一个公式。假设x为S中的第i+1大元素。那么x的展开项系数为：
i∑j=0(−1)j(ij)=(1−1)i=0i因此只有当i为0时，系数为1，其它情况都为0。第二个公式同理可证。
提供一些题目：
k-th min-max容斥
定义mink(S)表示S中第k小的数，对应的记maxk(S)表示S中第k大的数。
kmax(S)=∑T⊆S(−1)|T|−k(|T|−1k−1)min(T)kmin(S)=∑T⊆S(−1)|T|−k(|T|−1k−1)max(T)证明如下：
仅证明maxk(S)的展开公式，mink(S)的展开公式类似。
考虑第x+1大的数的系数：
x∑i=0(−1)i+1−k(ik−1)(xi)=x∑i=k−1(−1)i+1−k(xk−1)(x−(k−1)i−(k−1))=(xk−1)x−(k−1)∑i=0(−1)i(x−(k−1)i)=(xk−1)(1−1)x−(k−1)=[x=k−1]因此只有第k大的数正好贡献一次。
提供一些题目：