二项式反演学习笔记
ssy666666
·
·
算法·理论
二项式反演
二项式反演其实很像容斥的形式，我们先看一个例子：
考虑一个容斥：
设有一个数 A。那么有：
A = \sum_{j=0}^n (-1)^{j} \binom{n}{j} A
其中 A \in [1,n]。
显然有：
n-A = n - \sum_{j=0}^n (-1)^{j} \binom{n}{j} A
也有：
A = n - \sum_{j=0}^n (-1)^{j} \binom{n}{j} (n-A)
简单证明：这里相当于是让 A 变成它的“补集”(n-A)，右侧就是全集减去原集。
令 f(i)=A,g(i)=n-A。特别的，我们令 f(0)=g(0)=n。
代换，得到：
g(n)=\sum_{i=0}^n (-1)^i \binom{n}{i}f(i)
\\
f(n)=\sum_{i=0}^n (-1)^i \binom{n}{i}g(i)
这就是二项式反演的第一种形式。当然上面这个例子太特殊了，我们还是补一个详细的证明。
证明思路就是把 f 带到 g 的式子中去，然后推式子。
:::info[具体证明]
f(n)=\sum_{i=0}^n (-1)^i \binom{n}{i} \sum_{j=0}^i (-1)^j \binom{i}{j}f(j)
交换枚举顺序：
f(n) = \sum_{j=0}^n (-1)^j f(j) \sum_{i=j}^n (-1)^i \binom{n}{i}\binom{i}{j}
这里给出一个式子：
\binom{i}{j} \binom{j}{k}=\binom{i}{k}\binom{i-k}{j-k}
证明考虑组合意义：左边相当于在 i 个球里选 j 个球，再在 j 个球里选 k 个球，右边相当于先把 k 个球选出来，再选剩下的 i-k 个球。
把这个东西给带进去：
f(n) = \sum_{j=0}^n (-1)^j f(j) \sum_{i=j}^n (-1)^i \binom{n}{j}\binom{n-j}{i-j}
这样 \binom{n}{j} 就与 i 无关了，可以提到前面去，得到：
f(n) = \sum_{j=0}^n (-1)^j \binom{n}{j} f(j) \sum_{i=j}^n (-1)^i \binom{n-j}{i-j}
把后一项的 i 变成 i-j 得到：
f(n) = \sum_{j=0}^n (-1)^j \binom{n}{j} f(j) \sum_{i=0}^{n-j} (-1)^{i+j} \binom{n-j}{i}
把两个 -1 的幂次合并一下：
f(n) = \sum_{j=0}^n \binom{n}{j} f(j) \sum_{i=0}^{n-j} (-1)^{i+2j} \binom{n-j}{i}
一个显然的性质：\forall k \in \mathbb{Z}, (-1)^{2k}=1。
因此有：
f(n) = \sum_{j=0}^n \binom{n}{j} f(j) \sum_{i=0}^{n-j} (-1)^{i} \binom{n-j}{i}
后面这一坨一看就很像二项式定理对吧，我们给他补一个 1^k 上去：
f(n) = \sum_{j=0}^n \binom{n}{j} f(j) \sum_{i=0}^{n-j} (-1)^{i} 1^{n-j-i} \binom{n-j}{i}
得到：
f(n) = \sum_{j=0}^n \binom{n}{j} f(j) (1+(-1))^{n-j}
f(n) = \sum_{j=0}^n \binom{n}{j} f(j) 0^{n-j}
当 j=n 时 0^0 显然会炸，其他时候 0^k=0，消掉了。我们特殊考虑一下 j=n，你发现式子变成了这样：
f(n)=\binom{n}{n}f(n) (-1)^0 \binom{0}{0}
这个右边显然与左边相等对吧。
证明大致就是这样，后续的大多也和这个思路相同。
:::
上面这种形式可以说是挺少见的，因为完全就是一个容斥的样子。
我们考虑令 h(n)=(-1)^n g(n)，代换一下就有：
f(n)=\sum_{i=0}^n \binom{n}{i} h(i)
\frac{h(n)}{(-1)^n} = \sum_{i=0}^n (-1)^i \binom{n}{i}f(i)
h(n)=\sum_{i=0}^n (-1)^{n+i} \binom{n}{i}f(i)
显然 (-1)^{2i}=1，因此有：
h(n)=\sum_{i=0}^n (-1)^{n-i} \binom{n}{i}f(i)
然后你发现在具体证明中，我们并没有用到 i=0 这一性质，所以实际上，还有一个更通用的形式：
f(n)=\sum_{i=m}^n \binom{n}{i} h(i)
h(n)=\sum_{i=m}^n (-1)^{n-i} \binom{n}{i}f(i)
这是第二种形式。类似的，还有第三种形式：
f(n)=\sum_{i=n}^m \binom{i}{n} h(i)
h(n)=\sum_{i=n}^m (-1)^{i-n} \binom{i}{n}f(i)
证明和上面差不多，感兴趣的可以试试。这里不再阐述了。
这个之所以好用，是因为如果 f(n) 表示在方案中钦定 n 个的方案数，g(n) 表示恰好选 n 个的方案数，那么 g(i) 会由 f(n) 转移 \binom{i}{n} 次。
需要注意的是，由于钦定不同，可能导致一种方案由于不同钦定而被多次计算入 f，这是正常情况。
例题
P10596 BZOJ2839 集合计数
板子题。
设 f(i) 表示钦定有 i 个相同元素（意思就是这 i 个相同元素必须包含，其他可能还有别的相同元素）选集合的方案数，g(i) 表示恰好只有 i 个相同元素的方案数，显然有：
f(i) = \binom{n}{i}2^{2^{n-i}}
又有：
f(i) = \sum_{j=i}^n \binom{j}{i} g_j
相当于你在 j 个里面选 i 个作为你钦定的。
由二项式反演可知：
g(i)=\sum_{j=i}^n (-1)^{j-i} \binom{j}{i} f_j
P4859 已经没有什么好害怕的了
也是一个板子题，难点在 dp。
:::info[hint1]
一个显然的转化，由于一颗糖果只有可能有两种状态：“比与它配对的药片能量大”或“比能量小”，因此可以转化为求比能量大的数量为 \frac{n+k}{2} 的方案数。
:::
:::info[hint2]
设 f(i) 表示钦定有 i 组配对满足糖果比药片能量大的方案数，设 g(i) 为恰好有 i 组。显然有：
f(i) = \sum_{j=i}^n \binom{j}{i} g(i)
由二项式反演可知：
g(i) = \sum_{j=i}^n (-1)^{j-i} \binom{j}{i} f(j)
:::info[hint3]
先对 a 和 b 排个序。考虑 dp，设 dp_{i,j} 表示前 i 个数，钦定有 j 组满足条件的方案数，设 a_i 比 cnt 个 b_j 大，那么有转移：
dp_{i,j} = dp_{i-1,j} + (cnt-j+1)dp_{i-1,j-1}
由于前面的 a_i'，若满足条件，匹配的位置一定满足 b_j<a_i，于是有上述转移。
| 那么 f(i) = (n-1)!dp_{n,i}。 |
第二类斯特林数通项公式
先给出定义：n \brace k 表示将 n 个数划分成 k 个非空集合的方案数。
设 f(i) 表示将 n 个数划分到 i 个集合（可以为空）的方案数，设 g(i) 表示将 n 个数划分到 i 个非空集合的方案数。那么有：
f(i) = i ^n
f(i) = \sum_{j=1}^i \binom{i}{j}g_j
g_i = \sum_{j=1}^i(-1)^{i-j} \binom{i}{j}f_j
由于斯特林数集合无标号，所以说：
{n \brace k} = \frac{1}{k!}\sum_{j=1}^k(-1)^{k-j} \binom{k}{j} j^n
二维二项式反演
上面的所有式子都可以拓展到二维。
g(n,m)=\sum_{i=0}^n \sum_{j=0}^m (-1)^{i+j} \binom{n}{i} \binom{m}{j} f(i,j)
\\
f(n,m)=\sum_{i=0}^n \sum_{j=0}^m (-1)^{i+j} \binom{n}{i} \binom{m}{j} g(i,j)
这里不再证明了，证明思路是大致相同的，感兴趣的可以自己整一下（虽然没啥必要）。
例题
P3158 [CQOI2011] 放棋子
这道题比较综合，二维二项式反演可以不用，但是也是一道很好的题目。思维难度中等。
:::info[hint1]
你发现每一行、每一列的贡献可以拆开来算，但是一颗棋子同时属于一行和一列，怎么做呢？
:::
:::info[hint2]
你发现可以将不同的棋子的贡献拆开来考虑。
:::
:::info[hint3]
考虑 dp。设 dp_{i,j,k} 表示前 i 种颜色，恰好占了 j 行 k 列的方案数。那么有：
dp_{i,j,k} = \sum_{p=1}^j \sum_{q=1}^k \binom{j}{p} \binom{k}{q} g_{i,p,q} dp_{i-1,j-p,k-q}
| 其中 g_{i,p,q} 表示第 i 种颜色的棋子恰好放在 p 行 q 列的方案数。 |
:::info[hint4]
考虑如何求 g。
看到恰好就可以往二项式反演去想一下。
设 f_{i,j,k} 表示将第 i 种颜色的棋子放在 p 行 q 列中，可以有行或列为空的方案数。设第 i 种颜色的棋子有 cnt 个。
那么有：
f_{i,j,k}=\binom{pq}{cnt}
f_{i,j,k}= \sum_{p=0}^j \sum_{q=0}^k \binom{j}{p} \binom{k}{q} g_{i,p,q}
由二维二项式反演可知：
g_{i,j,k} = \sum_{p=0}^j \sum_{q=0}^k (-1)^{j+k-p-q} \binom{j}{p} \binom{k}{q} f_{i,p,q}
:::