思路:
。。。用伯努利公式搞出 f() 的系数。。暴力 O(m2) 搞出 g() 的系数。
。。最后和式展开。。把外层 0..n 循环的 i 用 f(n) 做成因子。。降维到 O(m2) 整体复杂度 O(m2)。。
具体:
http://pan.baidu.com/s/1eQxMOLG
实现上的细节::
1.
。。这个题 模数*2 超 int 。。。我的 Int 类为了优化速度依赖了这个性质。。因此需要稍微重写。。。
另外 (注意要给 Int 类定义 单目负号,否则默认会强转成 int 再取负导致错误。)
2.
。。注意最后的 i 是从 0..n 的。。这会导致最后作为因子的 f(n),会多出一项 0^m 。。。这一项在 m = 0 的时候是有值的!。。
。。而我们的 f() 函数是从 1 标号的。。。。因此需要特判一下。。