我都已经高二了，却还不知\(1^2+2^2+3^2+4^2+...+n^2\)的通式，真是惭愧。
现在说说如何求\(n^k\)的前缀和。
如果k比较小，我们可以直接差分序列手算。否则，我们可以用神奇的矩阵乘法。
我们知道：\[(n+1)^k=\sum_{i=0}^k n^i \times C(k, i)\]
构造一个矩阵\(A_n\)：\[n^0,n^1,...n^k,Sn\]
那么我们就可以构造一个矩阵B，使得\[A_i \times B = A_{i+1}\]。
这篇东西好像有点短。。。
UPDATE：
可以用瓦格朗日插值做。