二项式反演学习笔记

二项式反演:

$$
\begin{aligned}
f_n=\sum_{i=0}^{n}(-1)^i {n \choose i} g_i
&\Leftrightarrow
g_n=\sum_{i=0}^{n}(-1)^i {n \choose i} f_i
\\
f_n=\sum_{i=0}^{n}{n \choose i} g_i
&\Leftrightarrow
g_n=\sum_{i=0}^{n}(-1)^{n-i} {n \choose i} f_i \end{aligned}
$$

简单应用

假设 $f(i)$ 表示大于等于 $i$ 的数对答案的贡献,求恰好为 $k$ 时对答案的贡献。

证明在上一篇题解,结论:

$$
\sum\limits_{i=k}^n (-1)^{i-k} {i \choose k} f_i
$$

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×