这回是广为人知题了。
自然数幂和：给定 \(n,k\)，求 \(\sum_{i=1}^{n} i^k\)，\(n\le 10^{18},k\le 2000\)。
本来以为用扰动法求自然数幂和很猎奇，结果一搜出来十来篇博客。唉我还是太菜了。
尝试扰动法处理。
设：
\[f_{k}=\sum_{i=1}^{n} i^k
\]
那么扰动一下：
\[f_{k}=\sum_{i=1}^{n} (i+1)^k-(n+1)^k+1
\]
二项式定理展开之：
\[f_{k}=\sum_{i=1}^{n} \sum_{j=0}^k \binom{k}{j}i^j -(n+1)^k+1
\]
\[f_{k}=\sum_{j=0}^k \binom{k}{j}\sum_{i=1}^n i^j-(n+1)^k+1
\]
\[f_k=\sum_{j=0}^k \binom{k}{j} f_j-(n+1)^k+1
\]
然后你发现 \(f_k\) 消了就炸了……
\[\sum_{j=0}^{k-1} \binom{k}{j} f_j-(n+1)^k+1=0
\]
既然 \(f_k\) 没了，那么我们不死心，继续扰动 \(f_{k-1}\)！
\[\sum_{j=0}^k \binom{k+1}{j} f_j-(n+1)^{k+1}+1=0
\]
\[\sum_{j=0}^{k-1} \binom{k+1}{j} f_j-(n+1)^{k+1}+1=-(k+1)f_k
\]
\[f_k=\dfrac{(n+1)^{k+1}-\sum_{j=0}^{k-1} \binom{k+1}{j} f_j-1}{k+1}
\]
\(O(k^2)\) 递推即可。