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。i^k を篩法で計算したら 217 ms だった。篩法で i がもつ素数 p を適当に一個求めておけば、$i^k= p^k * (i/p)^k$ と計算できる。

本番中もラグランジュ補間は考えていたのだけど、式いじりに夢中になってて頭を切り替えられなかった。