差分法
我们令 $S_t(n) = displaystyle sum_{k=0}^n k^t$，易得 $S_t(n) + (n+1)^t = displaystyle sum_{k=0}^n(k+1)^t$ ，可以用二项式定理化简为 $displaystyle sum_{k=0}^n sum_{i=0}^tinom{t}{i}k^i$，交换求和顺序得：
$S_t(n)+(n+1)^t = displaystyle sum_{i=0}^tinom{t}{i}sum_{K=0}^nk^i = displaystyle sum_{i=0}^tinom{t}{i}S_i(n)$
所以我们用$t+1$代替式子中的$t$就可以得到：
$(n+1)^{t+1} = inom{t+1}{t}S_t(n)+ displaystyle sum_{i=0}^{t-1}inom{t+1}{i}S_i(n)$
移项得到：
$ S_t(n) = frac{1}{t+1}((n+1)^{t+1} - displaystyle sum_{i=0}^{t-1}inom{t+1}{i}S_i(n))$
然后我们就得到了一种递推求自然数幂和的方法，并且注意到这个递推式还帮我们证明了t次的自然数幂和是一个t+1次多项式。
拉格朗日插值法
由差分法，我们知道t次的自然数幂和是一个t+1次多项式，可以去t+2个点值队求出这个多项式。
详见链接
伯努利数法
伯努利数原本就是处理等幂和的问题，可以推出
$$ sum_{i=1}^{n}i^k={1over{k+1}}sum_{i=1}^{k+1}C_{k+1}^i*B_{k+1-i}*(n+1)^i $$
因为
$$sum_{k=0}^nC_{n+1}^kB_k=0(B_0=1)$$
所以
$$ B_n={- {1over{n+1}}}(C_{n+1}^0B_0+C_{n+1}^1B_1+……C_{n+1}^{n-1}B_{n-1})$$
伯努利数的证明十分复杂，记住即可。
详见 链接
第一类Stirling数/第二类Stirling数
详见 链接
上面的这些做法，时间复杂度只与 $k$ 有关，还有一些算法涉及到 $n$，虽然不是很高效。
BM递推
我们知道 $k$ 次幂求和的是个 $k+1$ 次多项式，
同样，设前n项和为 $S(n)$，容易发现 $S(n)$ 是关于前 $k+2$ 项的线性递推式。
例如，$k=2$ 时，$S_n = 4S_{n-1} - 6S_{n-2} + 4S_{n-3} - S_{n-4}$
所以求出前 $k+2$ 项和，放入BM中即可，时间复杂度为 $O(k^2logn)$
详见 链接
参考链接：
1. https://zhuanlan.zhihu.com/p/31101275
2. https://blog.csdn.net/werkeytom_ftd/article/details/50741165