二项式反演再学笔记

首先摆一下二项式定理

$(a+b)^k=\sum_{i=0}^k \binom k i a^ib^{k-i}$

再摆一下二项式反演的式子

$g(n)=\sum_{i=1}^n \binom n i f(i) ⟺ f(n)=\sum_{i=1}^n (-1)^{n-i}\binom n i g(i)$

考虑证明。

将右边的式子带入左边的式子

$\begin{aligned} g(n) &=\sum_{i=1}^n\binom n i \sum_{j=1}^i(-1)^{i-j}\binom i j g(j)\\ & =\sum_{i=1}^n g(i)\sum_{j=i}^n(-1)^{j-i}\binom j i\binom n j\\ & =\sum_{i=1}^n g(i) \sum_{j=i}^n(-1)^{j-i}\frac{n!}{i!(j-i)!(n-j)!}\\ & =\sum_{i=1}^n g(i)\frac{n!}{i!}\sum_{j=i}^n\frac{(-1)^{j-i}}{(j-i)!(n-j)!}\\ & =\sum_{i=1}^n g(i)\frac{n!}{i!(n-i)!}\sum_{j=i}^n(-1)^{j-i}\frac{(n-i)!}{(j-i)!(n-j)!}\\ & =\sum_{i=1}^n \binom n ig(i)\sum_{j=i}^n(-1)^{j-i}\binom{n-i}{j-i} \end{aligned}$

若 $i\not= n$，最后面的式子用二项式定理展开下，即是 $(1-1)^n=0$。

若 $i=n$，则最后面的式子为 $1$。

$\therefore g(n)=\sum_{i=1}^n \dbinom n i f(i) ⟺ f(n)=\sum_{i=1}^n (-1)^{n-i}\dbinom n i g(i)$

还有第二种形式

$g(n)=\sum_{i=1}^n(-1)^i\binom n if(i)⟺f(n)=\sum_{i=1}^n(-1)^i\binom n ig(i)$

这个式子的证明与上面的差不多。

当然，也可以下标是后缀的形式。

$g(n)=\sum _{i=n}^N\binom inf(i)⟺f(n)=\sum_{i=n}^N(−1)^{i−n}\binom ing(i)$

还有一种证明，就是把柿子化为卷积的形式。

$\begin{aligned} &F(n)=\sum_{i=0}^n\binom niG(i)\\ &F(n)=\sum_{i=0}^n\frac{n!}{i!(n-i)!}G(i)\\ &\frac{F(n)}{n!}=\sum_{i=0}^n\frac 1{(n-i)!}\frac{G(i)}{i!} \end{aligned}$

由于 $e^x=\sum\limits_{i=0}\dfrac{x^i}{i!}$，那么 $F=G*e^x$，$G=F*e^{-x}$。

$G(n)=\sum_{i=0}^n(-1)^{i}\binom niF(i)$

注：上面的式子因为图方便 $i$ 从 $1$ 开始，其实应该从 $0$ 开始

错排问题

令 $f(i)$ 表示 $i$ 个球在不同位置的方案，$g(i)$ 为所有的排列方案。有

$g(n)=\sum_{i=0}^n\binom n if(i)\\ \begin{aligned} f(n)&=\sum_{i=0}^n (-1)^{n-i}\binom n i g(i)\\ & =\sum_{i=0}^n(-1)^{n-i}\frac{n!}{i!(n-i)!}\times i!\\ & =n!\sum_{i=0}^n(-1)^{n-i}\frac{1}{(n-i)!}\\ \end{aligned}$

然后化成递推式即可。这只是一个例子。

恰好和至多或少的转换

令 $f(n)$ 表示恰好有 $n$ 个 $\texttt{\color{black}w\color{red}ty}$ $\text{\color{deeppink}AK}$ 的方案数，$g(n)$ 表示至多有 $n$ 个 $\texttt{\color{black}w\color{red}ty}$ $\text{\color{deeppink}AK}$ 的方案数。有

$g(n)=\sum_{i=0}^n\binom ni f(i)$

反演可得：

$f(n)=\sum_{i=0}^n (-1)^{n-i}\binom n ig(i)$

有至多，当然也有至少。

$g(n)=\sum_{i=n}^N\binom inf(i)\rightarrow f(n)=\sum_{i=n}^N (-1)^{i-n}\binom in g(i)$

P4859 已经没有什么好害怕的了

有 $n$ 个 $a_i,b_i$，要求两两配对，使得 $a>b$ 的对数减去 $a<b$ 的对数等于 $k$，$k,n\in[0,2000],ab$ 中没有相同元素。

令 $a>b$ 的对数为 $x$ 个，则 $x-(n-x)=k$，$x=\dfrac{n+k}{2}$。把 $nk$ 模 $2$ 不同余的先判掉。

将 $a,b$ 从小到大排序，令 $g_{i,j}$ 表示前 $i$ 个 $a$ 中，有 $j$ 个匹配大于 $b$ 的方案数。

则有

$g_{i,j}=g_{i-1,j}+g_{i-1,j-1}\times (cnt_i-j+1)$

其中 $cnt_i$ 表示 $b$ 中小于 $a_i$ 的个数。

然后对于其余的 $i-j$ 个随便排列，就是 $(i-j)!$。然后令新的函数为 $h$。

二项式反演下，可得

$f_{n,\frac{n+k}{2}}=\sum_{i=\frac{n+k}{2}}^n\binom n i (-i)^{i-\frac{n+k}{2}}h_{n,i}$

时间是 $O(n^2)$。

CF997C Sky Full of Stars

有一个 $n \times n(n\le10^6)$ 的正方形网格，用红色，绿色，蓝色三种颜色染色，求有多少种染色方案使得至少一行或一列是同一种颜色。

令 $g(i,j)$ 表示钦定有 $i$ 行 $j$ 列是同一颜色，其他随意的方案数，$f(i,j)$ 表示恰好有 $i$ 行 $j$ 列的方案数。

有

$g(x,y)=\sum_{i=x}^n\sum_{j=y}^n\binom i x \binom j yf(i,j)\\ f(x,y)=\sum_{i=x}^n\sum_{j=y}^n(-1)^{i+j-x-y}\binom ix\binom jyg(i,j)$

其实就是两次反演。

考虑 $g(x,y)$ 怎么求。

$g(x,y)=\left\{ \begin{aligned} & \binom nx\binom ny3^{(n-x)(n-y)+1} & x\not=0,y\not=0\\ & \binom nx3^{x+n(n-x)} & x\not=0,y=0\\ & \binom ny3^{y+n(n-y)} & x=0,y\not=0\\ & 3^{n^2} & x=0,y=0 \end{aligned} \right.$

由于 "至少一行或一列是同一种颜色"，那么其实就是总方案数减去 $f(0,0)$。

$f(0,0)=\sum_{i=0}^n\sum_{j=0}^n(-1)^{i+j}g(i,j)$

令 $A,B,C$ 分别表示 $x,y$ 上面不同的状态的方案数（$B$ 有两种所以要乘 $2$）。

$\begin{aligned} A &=\sum_{i=1}^n\sum_{j=1}^n(-1)^{i+j}g(i,j)\\ &=\sum_{i=1}^n\sum_{j=1}^n(-1)^{i+j}\binom ni\binom nj3^{(n-i)(n-j)+1}\\ &=3^{n^2+1}\sum_{i=1}^n (-1)^i\times3^{-ni}\binom ni\sum_{j=1}^n\binom nj(-3^{i-n})^{j}\\ &=3^{n^2+1}\sum_{i=1}^n (-1)^i\times3^{-ni}\binom ni((1-3^{i-n})^n-1)\\ B&=2\sum_{i=1}^n(-1)^i\binom n i3^{i+n(n-i)}\\ &=2\times3^{n^2}\sum_{i=1}^n(-1)^i\binom ni(3^{1-n})^i\\ &=2\times 3^{n^2}\times ((1-3^{1-n})^n-1)\\ C&=3^{n^2} \end{aligned}$

最后答案是 $3^{n^2}-A-B-C=-A-B$。

P4491 染色

长度为 $n$ 的画布，有 $m$ 种颜色。若其中有 $k$ 个颜色恰好有 $S$ 占个位置，则画布的权值为 $W_k$，求所有画布权值和。

令 $G(n)$ 表示恰好有 $n$ 种颜色个数为 $S$ 的方案数，$F(n)$ 表示至少有 $n$ 种颜色数为 $S$ 的方案数。

那么 $F(x)$ 的组成就有从 $m$ 中选 $x$ 个的方案、从 $n$ 个中选出 $Sx$ 的方案、其余 $n-Sx$ 个位置的方案、$Sx$ 个位置内部的方案。

$\begin{aligned} F(x)&=\binom mx\binom n{Sx}(m-x)^{n-Sx}\prod_{i=0}^{x-1}\binom {S(x-i)}{S}\\ &=\binom mx(m-x)^{n-Sx}\binom n{Sx}\prod_{i=1}^x\frac{(iS)!}{S!((i-1)S)!}\\ &=\binom mx(m-x)^{n-Sx}\binom n{Sx}\frac{(Sx)!}{(S!)^x}\\ &=\binom mx(m-x)^{n-Sx}\frac{n!}{(S!)^x(n-Sx)!}\\ \end{aligned}$

$\begin{aligned} G(x)&=\sum_{i=x}^{m}(-1)^{i-x}\binom{i}{x}F(i) \end{aligned}$

然后用 $O(n^2)$ 暴力求出答案。

尝试用卷积的形式来表示它。

$\begin{aligned} &G(x)=\sum_{i=x}^{m}(-1)^{i-x}\binom{i}{x}F(i)\\ &G(x)\times x!=\sum_{i=x}^m(-1)^{i-x}\frac{i!}{(i-x)!}F(i)\\ \end{aligned}$

明显的，令 $A_{i}=i!F(i),B_i=\dfrac{(-1)^i}{(i)!}$，则 $G=A*B$。

使用 NTT，时间是 $O(n\log n)$。