二项式反演

如果我们现在有一个式子
$f_{n}=\sum\limits_{i=0}^{n}\binom{n}{i}g_{i}$
告诉我们所有的f，让我们求g
这时候就要用到二项式反演了。

$g_{n}=\sum\limits_{i=0}^{n}(-1)^{n-i}\binom{n}{i}f_{i}$
考虑直接代入
$g_{n}=\sum\limits_{i=0}^{n}(-1)^{n-i}\binom{n}{i}\sum\limits_{j=0}^{i}\binom{i}{j}g_{j}$
换一下枚举顺序
$g_{n}=\sum\limits_{j=0}^{i}g_{j}\sum\limits_{i=j}^{n}(-1)^{n-i}\binom{n}{i}\binom{i}{j}$
把后面两个组合数暴力展开可以得到
$\binom{n}{i}\binom{i}{j}=\binom{n}{j}\binom{n-j}{n-i}$
把所有和i无关的项都提前
$g_{n}=\sum\limits_{j=0}^{n}g_{j}\binom{n}{j}\sum\limits_{i=j}^{n}(-1)^{n-i}\binom{n-j}{n-i}$
发现后面这个
$\sum\limits_{i=j}^{n}(-1)^{n-i}\binom{n-j}{n-i}$ 就是二项式定理。
当 $j=n$ 时为1
其他时候为 $(-1+1)^{n-j}=0$
所以 $g_n=g_n$
结论得证

例题

BZOJ 2839 集合计数
 BZOJ 2839 集合计数题解
 Luogu 4859 已经没有什么好害怕的了
 Luogu 4859 已经没有什么好害怕的了题解