求n^k的前缀和

我都已经高二了，却还不知(1^2+2^2+3^2+4^2+...+n^2)的通式，真是惭愧。

现在说说如何求(n^k)的前缀和。

如果k比较小，我们可以直接差分序列手算。否则，我们可以用神奇的矩阵乘法。

我们知道：$$(n+1)^k=sum_{i=0}k n^i imes C(k, i)$$

构造一个矩阵(A_n)：$$n^0,n1,...n^k,Sn$$
那么我们就可以构造一个矩阵B，使得$$A_i imes B = A_{i+1}$$。

这篇东西好像有点短。。。

UPDATE：

可以用瓦格朗日插值做。