soj947

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

$f_m=\sum\limits_{i=0}^{n}a_i\sum\limits_{j=0}^i(-1)^j\binom{m}{j}\binom{n-m}{i-j}$

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

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

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

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

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

$=\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}$

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

$=\sum\limits_{i=0}^na_i[x^i]\sum\limits_{k=0}^{n-m}(2x)^k(1-x)^{n-k}\binom{n-m}{k}$

$=\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}$

$=\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$ 符号里面的值转化成另一个数组，两个分布算。

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

$=\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}$

发现没有，后面的柿子里只有 $k$ ！没有 $m$ ！

令 $g_k=\sum\limits_{i=0}^na_i\binom{n-k}{i-k}(-1)^{i-k}$

$ans=\sum\limits_{k=0}^{n-m}2^k\binom{n-m}{k}g_k$

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

这是 $50$ 分的暴力验证。

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

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

$2.$ $n,m$ 写反了

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

文章作者: ruogu