一个看起来特别高大上实际上也非常高大上的东西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 \times g(i)\)，g(i) = \(\Pi_{j=1,j!=i}^{k} \frac{k-x_j}{x_i-x_j}\) (神仙构造)
接下来我们发现：\(g(x)=(?1)^{d?i} \times\frac{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\)
原文：https://www.cnblogs.com/tyqtyq/p/11108287.html