===== 递推 =====

$令f_{k}(n)=\sum_{i=1}^{n}i^{k}$

$$
\begin{align}
f_{k+1}(n+1) 
& =f_{k+1}(n)+(n+1)^{k+1} &\\
& =1+\sum_{i=1}^{n}(i+1)^{k+1} &\\
& =1+\sum_{i=1}^{n}\sum_{j=0}^{k+1} \binom{k+1}{j} i^{j} &\\
& =1+\sum_{j=0}^{k+1}\binom{k+1}{j} \sum_{i=1}^{n} &\\
& =1+\sum_{i=0}^{k+1}\binom{k+1}{i} f_{i}(n) &\\
& =1+f_{k+1}(n)+(k+1)f_{k}(n)+\sum_{i=0}^{k-1}\binom{k+1}{i} f_{i}(n) &\\
\end{align}
$$

$得到了:(k+1)f_{k}(n)=(n+1)^{k+1}-1 - \sum_{i=0}^{k-1}\binom{k+1}{i} f_{i}(n)$

$可以写成: f_{k-1}(n)=\frac{(n+1)^{k}-1}{k} -
\frac{1}{k}\sum_{i=0}^{k-2}\binom{k}{i} f_{i}(n)$
===== 拉格朗日插值法 =====

对于$\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]$计算速度一样，而针对多次询问则需要利用生成函数计算伯努利数

===== 伯努利数以及生成函数 =====

$
B_{0}=1,B_{1}=-\frac{1}{2},B_{2}=\frac{1}{6}\\\\
B_{3}=0,B_{4}=-\frac{1}{30},B_{5}=0\\\\
B_{6}=\frac{1}{42},B_{7}=0,B_{8}=-\frac{1}{30}
$

$可以利用:B_{0}=1,
\sum_{i=0}^{n}B_{i}\binom{n+1}{i}=0 
\Rightarrow B_{n}=-\frac{1}{n+1}\sum_{i=0}^{n-1}B_{i}\binom{n+1}{i}
计算$

$$
\begin{align}
& \sum_{i=0}^{n-1}B_{i}\binom{n}{i}=0 &\\
& \sum_{i=0}^{n}B_{i}\binom{n}{i}=B_{n} (n > 1)&\\
& \sum_{i=0}^{n}\frac{1}{i!(n-i)!}B_{i} = \frac{B_{n}}{n!} (n > 1)&
\end{align}
$$

$
考虑C(x)=\sum_{i=0}^{\infty}\frac{B_{i}}{i!}x^{i}\\\\
有e^{x}C(x)=C(x)+x \quad (加x是因为n>1导致第一项缺失,而n=0时上述等式也是成立的)\\\\
得到关于\frac{B_{n}}{n!}的生成函数\frac{x}{e^{x}-1}
$

故可以利用递推$O(n^{2})$或利用NTT$O(nlogn)$预处理


伯努利数与自然数幂和关系为

$f_{k}(n-1)
=\sum_{i=0}^{n-1}i^{k}
=\frac{1}{k+1}\sum_{i=0}^{k}\binom{k+1}{i}B_{i}n^{k+1-i}$


$
考虑F(x)=\sum_{k=0}^{\infty}(\sum_{i=0}^{n-1}i^{k})\frac{x^{k}}{k!}\\\\
F(x)=\sum_{i=0}^{n-1}\sum_{k=0}^{\infty}i^{k}\frac{x^{k}}{k!}=\sum_{i=0}^{n-1}e^{ix}=\frac{e^{nx}-1}{e^{x}-1}\\\\
注意到C(x)=\frac{x}{e^{x}-1},F(x)=C(x)\frac{e^{nx}-1}{x},
\frac{e^{nx}-1}{x}=\sum_{i=0}^{\infty}\frac{n^{i+1}x^{i}}{(i+1)!}\\\\
F(x)中x^{k}系数\frac{f_{k}(n-1)}{k!}=\sum_{i+j=k}\frac{B_{i}}{i!}\frac{n^{j+1}}{(j+1)!}即可得到上述公式
$