二项式反演

若

\[ f(n)=\sum^{n}_{i=0} g(i) C_{n}^{i} \]
则
\[ g(n)=\sum^{n}_{i=0}(-1)^{n-i}f(i)C_{n}^{i} \]

证明：

代入\(g(i)\)得：
\[ g(n)=\sum^{n}_{i=0}(-1)^{n-i}C_{n}^{i}\sum_{j=0}^{i}g(j)C_{i}^{j} \]
改变枚举顺序可得：
\[ g(n)=\sum^{n}_{i=0}(-1)^{n-i}C_{n}^{i}C_{i}^{j}\sum_{j=0}^{i}g(j) \]

\[ g(n)=\sum_{j=0}^{n}g(j)\sum^{n}_{i=0}(-1)^{n-i}C_{n}^{i}C_{i}^{j} \]

我们可以通过暴力得到一个式子：
\[ C_{n}^{i}C_{i}^{j}= \frac{n!}{i!(n-i)!}\times\frac{i!}{j!(i-j)!}=\frac{n!}{j!(n-j)!}\times\frac{(n-j)!}{(n-i)!(i-j)!}=C^{j}_{n}C^{n-i}_{n-j} \]
把这个式子代入得：
\[ g(n)=\sum_{j=0}^{n}g(j)\sum^{n}_{i=0}(-1)^{n-i}C^{j}_{n}C^{n-i}_{n-j} \]
所以
\[ g(n)=\sum_{j=0}^{n}g(j)C^{j}_{n}\sum^{n}_{i=0}(-1)^{n-i}C^{n-i}_{n-j} \]
当\(i\ne n\)时，由二项式定理得：
\[ \sum^{n}_{i=0}(-1)^{n-i}C^{n-i}_{n-j}=（-1+1）^{n-j}=0 \]
所以（此时\(i= n\)）：
\[ g(n)=g(n)C^{n}_{n}=g(n) \]
证毕

例题

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

由题意得，\(k=\frac{n+k}{2}\) (和差问题)

我们首先先将\(a,b\)从小到大排序

设\(f[i][j]\)表示前\(i\)个\(a\)中，选了\(j\)个\(a\)使得\(a>b\) 得方案数

令\(last[i]\)表示\(b\)中最后一个\(<a[i]\)的数的编号

无非就是选和不选，于是我们很容易得出状态转移方程:
\[ f[i][j]=f[i-1][j]+(last[i]-j+1)*f[i-1][j-1] \]
这里我们遇见了一个二项式反演题目中得一个常见套路：至少和恰好

令\(g[i]\)表示至少选了\(i\)个的方案数，\(ans[i]\)表示恰好选了\(i\)的方案数（就是我们要的答案）

在先前的dp中，我们还剩下一些没有选的数，它们可以任意排列

于是：
\[ g[i]=f[n][i]*(n-i)! \]
对于每个\(g[i]\)，我们试图寻找它和所有比\(i\)大的\(j\)的\(ans[j]\)的关系

对于每个\(ans[j]\)中的每一种方案，我们可以从所有\(j\)个人中任意选择若干个人

所以我们得到：
\[ g[i]=\sum_{j=i}^{n}C_{j}^{i}ans[j] \]
由二项式反演得：
\[ ans[j]=\sum_{j=i}^{n}(-1)^{j-i}C^{i}_{j}g[j] \]
（代码被我Gu掉了)

二项式反演笔记

原文：https://www.cnblogs.com/ybwowen/p/10963195.html