容斥原理
容斥原理的式子
一般来说不会直接用容斥原理这个式子，而是考虑一种特殊情况：交集的大小只与交集的数量有关。也就是说，我们可以用 $f[x] $来表示 \(n\) 个集合的交集的大小。
对这个式子进行整理：
二项式反演
证明
设 \(g[x]\) 表示 \(x\) 个补集的交集的大小， \(S\) 为全集， \(f[x]\) 表示 \(x\) 个原集的交集大小，那么有：
同时，由于补集的补集就是原集，因此又有：
二项式因此得证。
形式
以下设 \(f(n)\) 表示 \(n\) 个补集的交集大小， \(g(x)\) 表示 \(n\) 个原集的大小，则公式可以写成
还有另外一种形式
\(f(n)=\sum\limits_{i=0}^n{n\choose i}g(i)\Leftrightarrow g(n)=\sum\limits_{i=0}^n(-1)^{n-i}{n\choose i}f(i)\)
最常用的形式公式如下：
\(f(n)=\sum\limits_{i=n}^m{i\choose n}g(i)\Leftrightarrow g(n)=\sum\limits_{i=n}^m(-1)^{i-n}{i\choose n}f(i)\)
证明的话，均可以将右式代入左式，具体操作，自己手算。
组合意义
记 \(f(n)\) 表示 "钦定选 \(n\) 个" \(g(n)\) 表示 "恰好选 \(n\) 个",则对于任意的 \(i≥n\) ,\(g(i)\) 在 \(f(n)\) 中被计算了 \(C_i^n\) 次，故 \(f(n)=\sum_{i=n}^{m}\) ，其中 \(m\) 是数目上界。
*钦定 \(n\) 个表示至少有这 \(n\) 个，恰好表示只有 \(n\) 个。题目中经常是通过一个求另一个，就行集合计数，通过钦定求恰好。
例题
集合计数
题目大意
一个有 \(n\) 个元素的集合有 \(2^n\) 个不同子集（包含空集），现在要在这 \(2^n\) 个集合中取出至少一个集合，使得它们的交集的元素个数为 \(k\) ，求取法的方案数模 \(10^9+7\) 。
题解
通过思考列出式子 \({C^i_n}(2^{2^{n-i}}-1)\) 。即钦定 \(i\) 个交集元素，则包含这 \(i\) 个的集合有 \(2^{n-i}\) 个；每个集合可选可不选，但不能都不选，由此可得此方案数。
接下来考虑上式与所求的关系：设 \(f(i)\) 表示钦定交集元素为某 \(i\) 个的方案数，\(g(i)\) 表示交集元素恰好为 \(i\) 个的方案数，则
\({C^k_n}(2^{2^{n-k}}-1)=f(k)=\sum\limits_{i=k}^n{i\choose k}g(i)\)
通过二项式反演求出 \(g(k)=\sum\limits_{i=k}^n(-1)^{i-k}{i\choose k}f(i)=\sum\limits_{i=k}^n(-1)^{i-k}{i\choose k}{n\choose i}(2^{2^{n-i}}-1)\)
使用一些预处理手段，时间复杂度 \(O(n)\) 。
这里对于 \(2^{2^{n-i}}\) 取模，这里可以进行预处理，定义 \(base[i]\) 数组，\(base[i]=2^{2^{n-i}}\)
，则 $base[i]=base[i-1]^2 mod $ \(p\) 即可。