晚自习对反演理解加深的灵感记录

· · 算法·理论

当时在想二项式反演咋正向推导。

若

f_n = \sum_{i=0}^n {n \choose i} g_i

则

g_n = \sum_{i=0}^n (-1)^{n-i} {n \choose i} f_i

证明不难，把 f_i 展开即可。

但，我不明白推导思路。

然后自己玩：

f_n = \sum_{i=0}^n {\frac {n!} {i!(n-i)!}} g_i

然后做一点基础的参变分离。

\frac{f_n}{n!} = \sum_{i=0}^n \frac {1}{(n-i)!} \cdot \frac {g_i}{i!}

我了钢蛋雷塞球爆猪刚烈雷爆雷塞刚球啊。

这不是

\^F(x) = e^x \cdot \^G(x)

吗？

所以：

\^G(x) = e^{-x} \cdot \^F(x)

展开

g_n = \sum_{i=0}^n (-1)^{n-i}{n \choose i} f_i

嗯，行云流水的推导过程。

然后我还总结归纳了一下：容斥反演就是找反函数。

理由如下。

若

F(x)=H(G(x))

容斥就是在找

H'(H(x))=x

这样一来

G(x)=H'(F(x))

像上面那个例子里

我们知道

H(y)=e^xy

然后找到

H'(y)=e^{-x}y