这里就记一下推导过程。
前置芝士：
伯努利数：\(B_i\)。
定义：
\[\frac{x}{e^x-1}=\sum_{i=0}^{\infty}B_i\frac{x^i}{i!}
\]
\[e^x=\sum_{i=0}^{\infty}\frac{x^i}{i!}
\]
记
\[S_k(n)=\sum_{i=1}^{n}i^k
\]
那么
\[\begin{aligned}
F(x)&=\sum_{k=0}^{\infty}S_k(n)\frac{x^k}{k!}\\
&=\sum_{i=1}^{n}\sum_{k=0}^{\infty}\frac{(ix)^k}{k!}\\
&=\sum_{i=1}^{n}e^{ix}\\
&=\frac{e^{(n+1)x}-1}{e^x-1}-1\\
&=\frac{e^{(n+1)x}-1}{x}\cdot\frac{x}{e^x-1}-1
\end{aligned}
\]
然后
\[\begin{aligned}
\frac{e^{(n+1)x}-1}{x}&=\frac{1}{x}\sum_{m=1}^{\infty}\frac{[(n+1)x]^m}{m!}\\
&=\sum_{l=0}^{\infty}(n+1)^{l+1}\frac{x^l}{(l+1)!}
\end{aligned}
\]
于是
\[\begin{aligned}
F(x)+1&=\left(\sum_{l=0}^{\infty}(n+1)^{l+1}\frac{x^l}{(l+1)!}\right)\left(\sum_{i=0}^{\infty}B_i\frac{x^i}{i!}\right)\\
&=\sum_{k=0}^{\infty}\left[\sum_{i=0}^{k}\frac{(n+1)^{k-i+1}}{i!(k-i+1)!}B_i\right]x^k
\end{aligned}
\]
所以
\[\begin{aligned}
\frac{S_k(n)}{k!}&=\sum_{i=0}^{k}\frac{(n+1)^{k-i+1}}{i!(k-i+1)!}B_i\\
S_k(n)&=\frac{1}{k+1}\sum_{i=0}^{k}\binom{k+1}{i}B_i(n+1)^{k-i+1}
\end{aligned}
\]
\(B_i\) 可以 \(O(n^2)\) 递推，也可以 \(O(n\log n)\) 用 FFT。
反正就很好玩了。
 agent和组件)