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

$g_{n}=sumlimits_{i=0}^{n}(-1)^{n-i}binom{n}{i}f_{i}$
考虑直接代入
$g_{n}=sumlimits_{i=0}^{n}(-1)^{n-i}binom{n}{i}sumlimits_{j=0}^{i}binom{i}{j}g_{j}$
换一下枚举顺序
$g_{n}=sumlimits_{j=0}^{i}g_{j}sumlimits_{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}=sumlimits_{j=0}^{n}g_{j}binom{n}{j}sumlimits_{i=j}^{n}(-1)^{n-i}binom{n-j}{n-i}$
发现后面这个
$sumlimits_{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 已经没有什么好害怕的了 题解