某島

… : "…アッカリ~ン . .. . " .. .
June 13, 2014

TYVJ 1858. xlkxc

思路:

。。。用伯努利公式搞出 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 標號的。。。。因此需要特判一下。。