自然数幂和

记 $S_k(n)={\sum }_{i=0}^n{i}^k$。

固定 $n$

$S_k(n)+(n+1{)}^k={\sum }_{i=0}^n(i+1{)}^k={\sum }_{i=0}^k\left(\genfrac{}{}{0ex}{}{k}{i}\right)S_i(n)$

$S_k(n)=\frac{1}{k+1}((n+1{)}^{k+1}-{\sum }_{i=0}^{k-1}\left(\genfrac{}{}{0ex}{}{k+1}{i}\right)S_i(n))$

然后分治 ntt。

还有一个跟 $e$ 相关的求逆的做法，不会。

固定 $k$

由递推式，是 $k+1$ 次多项式，求出 $k+2$ 个点值插值。

还可以 BM $O(k^2\log n)$，不会。