Educational Codeforces Round 7 F. The Sum of the k-th Powers
これは解けないとまずいやつだった。
解法
$F(m)=\sum_{i=1}^{m} i^k$ は $k+1$ 次式になるので、ラグランジュ補間を用いることにより $F(0),F(1),...,F(k+1)$ から $F(n)$ を求めることができる。
$F(n)$ が $k+1$ 次式になるのは $(n+1)^k-n^k$ を使って帰納的に総和を求める手法により示せる。
ちなみにこれは次の問題の解答コードがあれば貼るだけである。
そのまま投げたら 1341 ms。
(2016/08/22) 多項式補完を O(n) のバージョンに変えた。639 ms。ik を篩法で計算したら 217 ms だった。 篩法で i がもつ素数 p を適当に一個求めておけば、$i^k= p^k * (i/p)^k$ と計算できる。
Educational Codeforces Round 7 F. The Sum of the k ...
本番中もラグランジュ補間は考えていたのだけど、式いじりに夢中になってて頭を切り替えられなかった。