一个看起来特别高大上实际上也非常高大上的东西qwq
我们要计算的是：(sum_{i=1}^{n} i^k)
现在我们假设k已经确定，令原式=f(n)
通过观察我们发现原式是一个k次多项式，考虑求出他的表达式，由代数基本定理可得只要求出k个点的值就可以唯一确定原多项式（至于怎么确定请看后文），接下来考虑我们二话不说先求一波值，因为只要带入k个数(1~k)就可以了，设这些点为((x_i,y_i))
那么原多项式=(sum_{i=1}^{k} y_i imes g(i))，g(i) = (Pi_{j=1,j!=i}^{k} frac{k-x_j}{x_i-x_j}) (神仙构造)
接下来我们发现：(g(x)=(−1)^{d−i} imesfrac{n(n−1)…(n−i+1)(n−i−1)…(n−d)}{i!(d−i)!}) ，通过恰当的预处理可以求出
例题（LuoguP5437）
求(frac{n}{2} sum{i=1}{n} sum{j=i+1}^{n} (i+j)^k)