【算法】关于二维二项式反演的正确性 -永无岛

前言

我第一次看到这个 idea 是神 $Fuyuki$ 去年 6 月份的时候出了一套题目，里面用到了这个东西，不过他当时没有给出证明。后来看到了 $boshi$ 在 $Mina$ 上发的计数合集，里面证明了这玩意儿的正确性，我个人认为还是一个非常妙的东西，所以专门开个坑记录一下。

柿子

$$
\text{if} \quad f_{n,m}=\sum_{i=0}^{n} \sum_{j=0}^{m}(\binom{n}{i} \binom{m}{j}g_{i,j}) \\
\text{then} \quad g_{n,m}=\sum_{i=0}^{n} \sum_{j=0}^{m}((-1)^{(n+m-i-j)}\binom{n}{i} \binom{m}{j}f_{i,j}) \\
$$

proof

$step 1:$ 变成能二项式反演的形式
令 $F_{i}=f_{i,m}$ ,$G_{i}=\sum_{j=0}^{m} \binom{m}{j} g_{i,j}$
原式变为 $F_n=\sum_{i=0}^{n}\binom{n}{i}G_i$
直接反演一波 $G_n=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}F_i$
再展开回去 $\sum_{j=0}^{m} \binom{m}{j} g_{n,j}=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}f_{i,m}$
注意，第一步是把 $m$ 视为了一个常量。

$step 2:$ 再二项式反演一遍
令 $F_{i}=\sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}f_{j,i}$ , $G_{i}= g_{n,i}$
原式变为 $F_m=\sum_{i=0}^{m}\binom{m}{i}G_i$
直接反演一波 $G_m=\sum_{i=0}^{m}(-1)^{m-i}\binom{m}{i}F_i$
再展开回去 $g_{n,m}=\sum_{i=0}^{m}(-1)^{m-i}\binom{m}{i}\sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}f_{j,i}$
$i,j$ 互换（就是换个名字，看起来比较亲切）$g_{n,m}=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}\sum_{j=0}^{m}(-1)^{m-j}\binom{m}{j}f_{i,j}$
整理一下，求和符号提前，就是开头的柿子力！

高维二项式反演也可以类似地推，如果省选前有时间的话会加上来的。