子集反演 一般有一个很套路的方法。 比如现在有一个全集条件集合 \(U\)。 现在要求恰好 \(S\) 集合满足，\(U-S\) 集合不满足的方案数，设其为 \(f_S\)，然而这个并不能直接算出。 有一个比较好算的东西是，钦定 \(T\) 集合满足，不管 \(U-T\) 集合是否满足的方案数，设其为 \(g_T\)。 显然有 \(g_S=\sum\limits_{S \in T} f_T\) 然后我们可以根据子集反演得到 \(f_S=\sum \limits_{S \in T} g_T(-1)^{|T|-|S|}\) 这样的话就可以算出要求的方案数了。

这个玩意正确的原因是这样的。 可以直接把前一个式子代入后一个式子，会得到 \(f_S=\sum \limits_{S \in T} \sum \limits_{T \in Z}f_Z (-1)^{|T|-|S|}\) \(=\sum \limits_{S\in Z}f_Z\sum \limits_{S \in T,T \in Z} (-1)^{|T|-|S|}\) \(=\sum \limits_{S\in Z}f_Z\sum \limits_{T \in Z-S} (-1)^{|T|}\) \(=\sum \limits_{S\in Z}f_Z[S=Z]=f_S\)

可能你们做过一道叫做小星星的题。 https://www.luogu.com.cn/problem/P3349 题意大概就是要找一个1~n的排列，来给每个节点重新编号，使得树上相邻的编号之间存在一条边。 这题中的限制实际上就是 1.\(n\) 个点均出现在用来编号的排列中。 2.相邻的编号存在边。 所以考虑这样一个做法，首先将排列这个限制去掉，转化为任意编号。 钦定集合 \(S\) 不出现在编号序列中，然后做一个简单的树形 \(dp\) 来统计这样的方案数 \(g_S\)。 套用上面的式子（其实现在求的就是 \(f_0\) ），我们知道 \(ans=\sum \limits_{S} g_S (-1)^{|S|}\)。

二项式反演 这个东西就与子集反演比较类似了。 如果现在的条件集合与具体哪些没有关系，而只与集合大小有关。 同样钦定若干个条件满足，设为 \(g_i\)。 将恰好的方案数设为 \(f_i\)。 有（注意这个组合数 \(\binom{k}{i}\) ） \(g_i=\sum \limits_{i \leq k}f_k\binom{k}{i}\) 然后根据二项式反演可以得到 \(f_i=\sum \limits_{i \leq k}g_k\binom{k}{i}(-1)^{k-i}\)

同样用代入的方法证明，将前一个式子代入后一个。 \(f_i=\sum \limits_{i \leq k}\sum \limits_{k \leq j}f_j\binom{j}{k}\binom{k}{i}(-1)^{k-i}\) \(=\sum \limits_{i \leq j}f_j \sum \limits_{i \leq k \leq j}\binom{j}{k}\binom{k}{i}(-1)^{k-i}\) \(=\sum \limits_{i \leq j}f_j \sum \limits_{i \leq k \leq j}\binom{j}{i}\binom{j-i}{k-i}(-1)^{k-i}\) \(=\sum \limits_{i \leq j}f_j \binom{j}{i} \sum \limits_{k=0}^{j-i}\binom{j-i}{k}(-1)^k\) \(=\sum \limits_{i \leq j}f_j \binom{j}{i} (1-1)^{j-i}=f_i\)

可能你们做过一道叫做集合计数的题。 题目大意 一个有 \(n\) 个元素的集合有 $2n$ 个不同子集（包含空集）. 现在要在这 $2n$ 个集合中取出至少一个集合，使得它们的交集的元素个数为 \(k\) ，求取法的方案数。 $1 \leq n \leq 10^6 ，0 \leq k \leq n$ 。 这题的做法是这样的。 要求的是交集大小恰好为 \(k\) ，设为 \(f_k\)。 有一个容易算出的东西是钦定交集大小至少为 \(k\)，设为 \(g_k\)。 有 \(g_k=\binom{n}{k} (2^{2^{n-k}}-1)\) \(g_k=\sum \limits_{i \geq k} \binom{i}{k}f_i\) 所以可以套用二项式反演的式子得到 \(f_k=\sum \limits_{i \geq k}\binom{i}{k}(-1)^{i-k}g_i\)

很抱歉，这次讲课准备的很仓促。 下次一定（好好讲）。