题意

计算\(\sum _{i=1}^{n}i^k=1^k+2^k+\cdots +n^k\)。

题解

先利用拉格朗日插值法,计算出\(\sum _{i=1}^{n}i^k=1^k+2^k+\cdots +n^k\)的多项式形式。

根据给出的性质,显然\(\sum _{i=1}^{n}i^k=1^k+2^k+\cdots +n^k\)是一个最高项次数为\(k+1\)的多项式,那么我们需要\(k+2\)个坐标来表示,不妨用\(1,\cdots ,k+2\)作为\(x\)来差值。

于是我们得到的多项式为\(F(x)=\sum _{j=1}^{k+2} y_j \prod _{i=1,i\neq j}^{k+2} \frac{x-x_i}{x_j-x_i}\)。

而显然,这道题目的答案就是\(F(n)\),而且\(x_i=i\)。

于是我们预处理\(y_j\)和\(A_{n}^{k}\)就可以了。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注