二项式反演
鸽了好久的二项式反演。
反演本质上是给你一个数列 \(g\) ，\(g_n=\sum\limits_{i=0}^{n}a_{n,i}f_i\) 。
让你去求 \(f\) 。
发现其实本质上是一个 行向量\(g\)，等于另外一个行向量 \(f\)，乘上系数矩阵。
反演的过程相当于求出了系数矩阵的逆矩阵。
二项式反演想说的是什么呢？ \[ g_n=\sum\limits_{i=0}^{n} (-1)^i\binom{n}{i}f_i\Leftrightarrow f_n=\sum\limits_{i=0}^{n} (-1)^i\binom{n}{i}g_i \] 证明后说，当你发现这两个式子竟然如此相似的时候，你应该感到十分震惊对不对。
因为这个系数矩阵的逆矩阵竟然是他自己。 \[ g_n=\sum\limits_{i=0}^{n} (-1)^i\binom{n}{i}f_i\Leftrightarrow f_n=\sum\limits_{i=0}^{n} (-1)^i\binom{n}{i}g_i\\ 同时显然有 g_n=\sum\limits_{i=0}^{n}\binom{n}{i}f_i\Leftrightarrow f_n=\sum\limits_{i=0}^{n} (-1)^{n-i}\binom{n}{i}g_i \]
那先考虑证明。
运用 \(EGF\) 的知识，有： \[ \frac{g_n}{n!}=\sum_{i=1}^{n}\frac{1}{(n-1)!}\cdot\frac{f_i}{i!} \] 上式显然是卷积形式，设 \(G\) 是 \(g_n\) 的生成函数 ，\(F\) 是 \(f_n\) 的生成函数。 \[ \begin{aligned} G&=e^{x}\times F\\ F&=G\times e^{-x}\\ [n]e^{-x}&=\frac{(-1)^n}{n!}\\ \frac{f_n}{n!}&=\sum\limits_{i=0}^{n}\frac{(-1)^{n-i}}{(n-i)!}\cdot\frac{g_i}{i!}\\ f_n&=\sum\limits_{i=0}^{n}(-1)^{n-i}\binom{n}{i}g_i \end{aligned} \]
直接带入。 \[ \begin{aligned} f_n&=\sum\limits_{i=0}^{n}(-1)^{n-i}\frac{n!}{i!\times (n-i)!}\sum_{j=0}^{i}\frac{i!}{j!\times(i-j)!}f_j\\ f_n&=\sum_{j=0}^{n}\frac{n!}{j!}\sum_{i=j}^{n}(-1)^{n-i}\frac{f_j}{(n-i)!(i-j)!}\\ f_n&=\sum_{j=0}^{n}\frac{n!}{j!}f_j\sum_{i=0}^{n-j}(-1)^i\frac{1}{i!((n-j)-i)!}\\ f_n&=\sum_{j=0}^{n}\binom{n}{j}f_j\sum_{i=0}^{n-j}(-1)^i\binom{n-j}{i}\\ f_n&=\sum_{j=0}^{n}\binom{n}{j}f_j(1-1)^{n-j}\\ \end{aligned} \] 显然只有当 \(n=j\) 时，后面的系数才不是 \(0\)。
也就是 \(f_n=\sum\limits_{j=n}^{n}\binom{n}{j}f_j\) ,也就是 \(f_n=f_n\)。
你知道二项式反演的四种写法吗？
有 ： \[ g_n=\sum_{i=n}^{}(-1)^i\binom{i}{n}f_i\Leftrightarrow f_n=\sum_{i=n}^{}(-1)^i\binom{i}{n}g_i \] 这个证明可以由初始系数矩阵，翻转行列证明。由于初始的矩阵的逆矩阵等于本身，性质比较好。
可以说明初始矩阵的转置的逆矩阵也是该矩阵的转置。
\(A=A^{-1}\Leftrightarrow A^T={A^T}^{-1}\)
所以我们现在有4种二项式反演形式。 \[ \begin{aligned} g_n=\sum\limits_{i=0}^{n} (-1)^i\binom{n}{i}f_i&\Leftrightarrow f_n=\sum\limits_{i=0}^{n} (-1)^i\binom{n}{i}g_i\\ g_n=\sum\limits_{i=0}^{n}\binom{n}{i}f_i&\Leftrightarrow f_n=\sum\limits_{i=0}^{n} (-1)^{n-i}\binom{n}{i}g_i\\ g_n=\sum_{i=n}^{}(-1)^i\binom{i}{n}f_i&\Leftrightarrow f_n=\sum_{i=n}^{}(-1)^i\binom{i}{n}g_i\\ g_n=\sum_{i=n}^{}\binom{i}{n}f_i&\Leftrightarrow f_n=\sum_{i=n}^{}(-1)^{i-n}\binom{i}{n}g_i \end{aligned} \] 例题
是这样的，我在一段时间内，对于 \(O(n^2)\) 级别的可二项式反演题我是这么做到。
就是考虑容斥，定义我们钦定的答案是 \(f\)，真实答案是 \(g\)。
\(f\) 会咋什么时候算重，对于 \(f_i\) 我们枚举 \(j>i\) ,含义是假如恰好选 \(j\) 个会算重多少次。
\(f_i=f_i-\binom{j}{i}g_j\) 这样把这个恰好减去，（考虑 \(j\) 个位置我们对于能钦定 \(\binom{j}{i}\) 次）。
反枚举 \(i\) 更新即可。
这个其实就是 \(g_i=f_i-\sum_{j>i}\binom{j}{i}g_j\),这是个方程，移项 \(f_i=\sum_{j>i}\binom{j}{i}g_j+g_i=\sum_{j\ge i}\binom{j}{i}g_j\)。
所以这个严格弱于二项式反演，可拓展性不高。