考虑下面的问题:
其中\(w,g,s\)为任意数字，求\(f\)。
暴力转移是\(O(N^2M^2)\)的。
用多项式乘法可以\(O(N^2M\log M)\)常数较大。
下面讨论一种\(O(N^2M)\)的小常数做法。
首先需要对组合数进行一步转换：\({m\choose n}=[x^n](1+x)^m\)。
则式子就可以写成：
其中\(h_{i}=\sum_{j\geq 0} {w_i\choose j}x^j\)。
定义\(f‘\)表示\(f\)左移\(1\)得到的多项式。
则上面的式子就是:
其实就是右移，相加。
最后通过\(f‘\)还原到\(f\)只需要实现右移\(1\)即可。
代码非常好写。
例题：SRM 761 div1 Level 3 SpanningSubgraphs
题解+代码：SRM 761 div1 Level 3 SpanningSubgraphs 题解 - QQQ,,, - 博客园 (cnblogs.com)
原文：https://www.cnblogs.com/gary-2005/p/14988619.html