読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

多項式補間

Educational Codeforces Round 7 F. The Sum of the k-th Powers

これは解けないとまずいやつだった。 codeforces.com 解法 $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-…