avatar

soj947

http://120.27.222.204:12243/problem/947

花的时间很久,我会一步一步简述怎么做。

fm=i=0naij=0i(1)j(mj)(nmij)f_m=\sum\limits_{i=0}^{n}a_i\sum\limits_{j=0}^i(-1)^j\binom{m}{j}\binom{n-m}{i-j}

=i=0nai[xi]{(1x)m(1+x)nm}=\sum\limits_{i=0}^na_i[x^i]\{(1-x)^m(1+x)^{n-m}\}

这一步利用了范德蒙恒等式生成函数证明的方法,这个柿子长得那么像范德蒙恒等式,就可以把他化成了类似生成函数的形式。

=i=0nai[xi](1x)m(1+x)nm=\sum\limits_{i=0}^na_i[x^i](1-x)^m(1+x)^{n-m}

=i=0nai[xi](1x)m(1x+2x)nm=\sum\limits_{i=0}^na_i[x^i](1-x)^m(1-x+2x)^{n-m}

这样一下子就变成只剩下一个二项式了!

=i=0nai[xi](1x)mk=0nm(2x)k(1x)nmk(nmk)=\sum\limits_{i=0}^na_i[x^i](1-x)^m\sum\limits_{k=0}^{n-m}(2x)^k(1-x)^{n-m-k}\binom{n-m}{k}

注意这里的kknmkn-m-k互换以后柿子会变麻烦,虽然也可以做,但是最后不要互换为好。

=i=0nai[xi]k=0nm(2x)k(1x)nk(nmk)=\sum\limits_{i=0}^na_i[x^i]\sum\limits_{k=0}^{n-m}(2x)^k(1-x)^{n-k}\binom{n-m}{k}

=i=0naik=0nm2k[xik](1x)nk(nmk)=\sum\limits_{i=0}^na_i\sum\limits_{k=0}^{n-m}2^k[x^{i-k}](1-x)^{n-k}\binom{n-m}{k}

=i=0naik=0nm2k(1)ik(nkik)(nmk)=\sum\limits_{i=0}^na_i\sum\limits_{k=0}^{n-m}2^k(-1)^{i-k}\binom{n-k}{i-k}\binom{n-m}{k}

这个柿子我看了好久,甚至一度怀疑他和原柿长得一样。。但是事实证明,像这样存在两个\sum的柿子也可以算,关键在于是否能把一个\sum符号里面的值转化成另一个数组,两个分布算。

其实这个时候已经具备了这种条件,只需要拨云即可见日,就差这关键的胜负手!

=k=0nm2k(nmk)i=0nai(nkik)(1)ik=\sum\limits_{k=0}^{n-m}2^k\binom{n-m}{k}\sum\limits_{i=0}^na_i\binom{n-k}{i-k}(-1)^{i-k}

发现没有,后面的柿子里只有kk!没有mm

gk=i=0nai(nkik)(1)ikg_k=\sum\limits_{i=0}^na_i\binom{n-k}{i-k}(-1)^{i-k}

ans=k=0nm2k(nmk)gkans=\sum\limits_{k=0}^{n-m}2^k\binom{n-m}{k}g_k

这时,终于发现上述两个柿子都是可以卷积的形式,这题就这么做完了。

http://120.27.222.204:12243/submission/79500

这是5050分的暴力验证。


这题在考场上,对于我来说应该算一道不太可做的题,因为自己化柿子能力比较弱。但是也总结一下这次画柿子出现的错误吧:

1.1.二项式展开忘记乘组合数

2.2.n,mn,m写反了

如果遇到相似的题,应该在关键的步骤处用程序验证!!!

文章作者: ruogu
文章链接: http://ruogu-alter.github.io/2020/05/20/soj947/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ruogu's blog

评论