二项式反演
用来解决奇怪的计数问题. 首先是数论之神的照片
![咕了, 有机会再拍]()
例题
都是 BZOJ 的, 当然后两道在洛谷上也有.
前置知识 (?)
其实严格来说并不算前置知识, 但窝感觉还是最好看一下.
什么是反演
给定一个数列 $\{f_x\}$ 求 $f_n$, 然而并不好直接求. 于是找到另一个数列 $\{g_x\}$ 与 $\{f_x\}$ 有关, 并且 $\{g_x\}$ 比较好求, 就用 $\{g_x\}$ 来表示 $\{f_x\}$. 当然出题人不会那么良心直接就让你求出怎么用 $\{g_x\}$ 来表示 $\{f_x\}$, 所以要先用 $\{f_x\}$ 表示 $\{g_x\}$, 然后用反演化成想要的柿子.
用窝们教练的话说就是
对于一个数列 $\{f_n\}$ 来说，如果我们知道另外一个数列 $\{g_n\}$，满足如下条件:
$$ g_n=\sum_{i=0}^na_{ni}f_i $$
反演就是利用：$g_0,g_1,\dots,g_n$ 来表示 $f_i$
$$ f_n=\sum_{i=0}^nb_{ni}g_i $$
$\delta$ 函数
定义
$$ \delta_{i,j}=\begin{cases} 1,&i=j\\ 0,&i\not=j \end{cases} $$
柿子 (们)
yysy 柿饼是真的难吃(呕).
基本柿
$$ f_n=\sum_{i=0}^n(-1)^i\dbinom nig_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^i\dbinom nif_i $$
其中 $\dbinom ni$ 表示组合数 $\mathrm C_n^i$ 即 $n$ 个元素选 $i$ 个的方案数这点就不用再说了吧.
变形柿
$$ f_n=\sum_{i=0}^n\dbinom nig_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}\dbinom nif_i\\ f_n=\sum_{i=n}^m\dbinom ing_i\Leftrightarrow g_n=\sum_{i=n}^n(-1)^{i-n}\dbinom inf_i $$
其实这几个柿子都是有证明的, 要用到上面的 $\delta$ 函数, 但是很复杂, 所以咕了.