前言

我第一次看到这个 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}$
整理一下,求和符号提前,就是开头的柿子力!

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

分类: 文章

darken

2018级退役OIer,QQ:2578050796。 博客园:https://www.cnblogs.com/thedreammaker/ 有问题请QQ联系,个人原因应该不会经常上OI相关网站了,不过如果有OI问题的话也可以来问我,但答不答的出来就说不准了QAQ

4 条评论

Qiuly · 2020年6月16日 2:50 下午

感谢您一直以来的贡献!

您的账户已经升级为 作者 啦!

    darken · 2020年6月16日 7:34 下午

    成为 作者 有什么好玩的地方吗/se

      Qiuly · 2020年6月17日 6:30 下午

      有更多权限吧 /qq

      貌似提交文章可以直接通过审核?记得不太清,好像还可以访问图库?/qq

      另外省选加油~

        darken · 2020年6月17日 6:34 下午

        谢谢!
        也祝 Qiuly 省选取得满意的成绩!

发表评论

电子邮件地址不会被公开。 必填项已用*标注