写了很久，很详细，望给个赞QwQ（

定理

$$f(n)=\sum \limits_{i=0}^{n} \binom{n}{i} g(i) \Leftrightarrow g(n)=\sum \limits_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)$$

证明

$\quad \sum \limits_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)$

$= \sum \limits_{i=0}^{n} (-1)^{n-i} \binom{n}{i} \sum \limits_{j=0}^{i} \binom{i}{j} g(j)$（将定理左边式子代入）

$= \sum \limits_{j=0}^{n} g(j) \sum \limits_{i=j}^{n} (-1)^{n-i} \binom{n}{i} \binom{i}{j}$ $①$（将两个 $\sum$ 调换一下位置）

$\quad \binom{n}{i} \binom{i}{j}$

$= \frac{n!}{i!(n-i)!} \cdot \frac{i!}{j!(i-j)!}$（把二项式系数拆开）

$= \frac{n!}{j!(n-j)!} \cdot \frac{(n-j)!}{(n-i)!(i-j)!}$（把 $i!$ 约掉，乘上 $(n-j)!$，稍微改变一下分母）

$= \binom{n}{j} \binom{n-j}{i-j}$ $②$（重新变成二项式系数）

$\therefore ①$

$= \sum \limits_{j=0}^{n} g(j) \sum \limits_{i=j}^{n} (-1)^{n-i} \binom{n}{j} \binom{n-j}{i-j}$（代入 $②$ 式）

$= \sum \limits_{j=0}^{n} \binom{n}{j} g(j) \sum \limits_{i=j}^{n} (-1)^{n-i} \binom{n-j}{i-j}$（将 $\binom{n}{j}$ 提出）

$= \sum \limits_{j=0}^{n} \binom{n}{j} g(j) \sum \limits_{i=0}^{n-j} (-1)^{(n-j)-i} \binom{n-j}{i}$ $③$（改成枚举 $i-j$）

二项式定理（不然这玩意儿为什么叫二项式反演）：

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

（长得跟我们的式子很像）

于是，我们发现：$\sum \limits_{i=0}^{n-j} (-1)^{(n-j)-i} \binom{n-j}{i} = {(1-1)}^{n-j} = 0^{n-j}$

那这个式子的结果不就是 $0$ 吗？！！

（如果你也这么认为，那么恭喜你，你可以看看这个）

我们知道，$0^0$ 是没有意义的，所以我们在指数（也就是 $n-j$）为 $0$ 的时候不能用二项式定理。

但 $n-j=0$ 的时候也非常显然：$\sum \limits_{i=0}^{0} (-1)^{0-i} \binom{0}{i} = \binom{0}{0} = 1$

$\therefore \sum \limits_{i=0}^{n-j} (-1)^{(n-j)-i} \binom{n-j}{i} = [j=n]$ $④$（将两种情况综合）

$\therefore ③$

$= \sum \limits_{j=0}^{n} \binom{n}{j} g(j) [j=n]$（代入 $④$ 式）

$= \binom{n}{n} g(n)$

$= g(n)$

证毕。

变体

$$f(n)=\sum \limits_{i=n}^{m} \binom{i}{n} g(i) \Leftrightarrow g(n)=\sum \limits_{i=n}^{m} (-1)^{i-n} \binom{i}{n} f(i)$$

证明思路与刚才相似，有兴趣的读者可以自行推导。

用途

设 $f(n)$ 表示钦定（可以感性理解为至少）选 $n$ 个时的值，$g(n)$ 表示恰好选 $n$ 个时的值，$m$ 为选的数目上限。

显然，$f(n) = \sum \limits_{i=n}^{m} \binom{i}{n} g(i)$。此时若要求 $g$，可以用二项式反演，求出 $f$ 之后再推出 $g$。

例题

[NOI Online #2 提高组] 游戏（AcWing）

[NOI Online #2 提高组] 游戏（洛谷）

思路：设 $f(k)$ 表示钦定 $k$ 次非平局时的期望，$g(k)$ 表示恰好 $k$ 次非平局时的期望。

二项式反演，然后用树上背包求 $f$ 即可。

时间复杂度：$\Theta(n^2)$