鲜花：不会说明你有抑郁症3

这回是广为人知题了。

自然数幂和：给定 \(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)\) 递推即可。