CVBB ACM Team

对于$\sum_{i=1}^n i^k=f[n][k]$，$f[][k]$具体表达是一个$k+1$次多项式，我们求解$f[0\sim k+1][k]$，然后进行插值即可

对于具体计算$f[n]=\sum_{i=0}^{k+1} f[i]\frac{\prod_{j=0,j\neq i}^{k+1}(n-j)}{\prod_{j=0,j\neq i}^{k+1}(i-j)}$

$\prod_{j=1,j\neq i}^{k+1}(n-j)=\prod_{j=1}^{i-1}(n-j)\prod_{j=i+1}^{k+1}(n-j)$是前缀积$\times$后缀积

$\prod_{j=0,j\neq i}^{k+1}(i-j)=i!(k+1-i)!(-1)^{k+1-i}$

于是，可以$O(k)$预处理$f[]$以及阶乘，前后缀然后$O(k)$计算

这种方法对不同$f[n]$计算速度一样，而针对多次询问则需要利用生成函数计算伯努利数