简介

自然数的 \(k\) 次幂求和，顾名思义，即求：

\[ S_k(n) = \sum_{i=1}^{n} i^k \]

待定系数法

我们观察几组式子：

\[ \begin{align*} S_1(n) &= \frac{n(n+1)}{2} \\ S_2(n) &= \frac{n(n+1)(2n+1)}{6}\\ S_3(n) &= \frac{n^2(n+1)^2}{4} \\ S_4(n) &= \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30} \\ \end{align*} \]

总结规律，我们可以大胆猜想，\(S_k(n)\) 的求和公式应该是一个 \(k+1\) 次多项式。

所以可以直接列出 \(k+1\) 个方程，解线性方程组。

证明在下一节给出。

差分法

可以得到： \[ S_k(n) = \frac{1}{k+1} \left[ (n+1)^{k+1} - 1 - \sum_{j=0}^{k-1} \binom{k+1}{j} S_j(n) \right] \]

证明

考虑相邻整数的 \(k+1\) 次幂差：

\[ (m+1)^{k+1} - m^{k+1} = \sum_{j=0}^k \binom{k+1}{j} m^j \]

对 \(m\) 进行求和：

\[ \sum_{m=1}^n[(m+1)^{k+1} - m^{k+1}] = \sum_{m=1}^n \sum_{j=0}^k \binom{k+1}{j} m^j \]

左边易得：

\[ (n+1)^{k+1} - 1 \]

右边变换：

\[ \begin{align*} &\sum_{m=1}^n \sum_{j=0}^k \binom{k+1}{j} m^j \\ =&\sum_{j=0}^k\binom{k+1}{j}\sum_{m=1}^nm^j\\ =& \sum_{j=0}^{k} \binom{k+1}{j} S_j(n) \end{align*} \]

因此得到恒等式：

\[ \sum_{j=0}^{k} \binom{k+1}{j} S_j(n) = (n+1)^{k+1} - 1 \]

分离 \(S_k\)：

\[ \begin{align*} \binom{k+1}{k} S_k(n) + \sum_{j=0}^{k-1} \binom{k+1}{j} S_j(n) &= (n+1)^{k+1} - 1\\ (k+1) S_k(n) &= (n+1)^{k+1} - 1 - \sum_{j=0}^{k-1} \binom{k+1}{j} S_j(n) \end{align*} \]

因此：

\[ S_k(n) = \frac{1}{k+1} \left[ (n+1)^{k+1} - 1 - \sum_{j=0}^{k-1} \binom{k+1}{j} S_j(n) \right] \]

这样我们不仅得到了一条递推式，还证明了 \(S_k(n)\) 的求和式是一个 \(k+1\) 次多项式。

直接递推，复杂度 \(k^2\)。

还可以用分治 FFT，复杂度 \(O(k\log^2 k)\)

拉格朗日插值

我们知道 \(S_k(n)\) 的求和式是一个 \(k+1\) 次多项式，当然可以用 \(k+2\) 个点进行插值。

取 \((0,S_k(0)), (1,S_k(1)), \cdots, (n,S_k(k+1))\) 作为 \(k+2\) 个点，得：

\[ S_k(n) = \sum_{i=0}^{k+1}S_k(i)\prod_{i\neq j}\frac{n-j}{i-j} \]

暴力是 \(k^2\) 的，考虑优化。

分别考虑积的分子与分母。

对于分母，考虑 \(i\) 已确定：

\[ \begin{align*} &\frac{1}{\prod_{i\neq j}(i-j)} \\ =&\frac{1}{i(i-1)(i-2)\cdots1\times(-1)\cdots(k+2-i-1)(k+2-i)} \\ =&(-1)^{k+2-i}\frac{1}{i!(k+2-i)!} \end{align*} \]

预处理阶乘与逆元即可。

对于分子:

\[ \begin{align*} &\prod_{i\neq j}(n-j)\\ =&n(n-1)\cdots\{n-(i-1)\}\{n-(i+1)\}\cdots\{n-(k+2)\}\\ =&\left\{\prod_{j=1}^{i-1}(n-j)\right\}\left\{\prod_{j=i+1}^{k+2}(n-j)\right\} \end{align*} \]

维护 \(n-j\) 的前缀积和后缀积即可。

复杂度 \(O(k\log V)\)，\(\log V\) 是逆元复杂度，也可以 \(O(n)\) 预处理优化。

伯努利数

有公式：

\[ S_k(n) = \frac{1}{k+1}\sum_{i=0}^k\binom{k+1}{i}B_in^{k+1-i} \]

其中 \(B_i\) 是伯努利数，定义为：

\[ B_n = \begin{cases} 1 & n=0 \\ -\frac{1}{2} & n=1\\ -\sum_{k=0}^{n-1}\binom{n}{k}B_k\frac{1}{n-k} & n\equiv 0 \pmod 2\ \text{且}\ n>1\\ 0 & \text{otherwise} \end{cases} \]

作者太菜了不会证明，可以参考 OI-Wiki

第一类 Stirling 数

这次我们对 \(S_k(n)\) 多加一个 \(0\)，即：

\[ S_k(n) = \sum_{i=0}^k i^k \]

根据第一类 Stirling 数定义：

\[ \binom{n}{k} = \frac{\prod_{i=n-k+1}^n i}{k!} = \frac{1}{k!}\left[\sum_{i=0}^k(-1)^{i+k}{k\brack i} n^i\right] \]

变形得：

\[ n^k ={\sum_{i=0}^{k-1}(-1)^{i+k}{k\brack i}n^i}-k! \binom{n}{k} \]

累加求和：

\[ \begin{align*} S_k(n) &= \sum_{j=0}^n\left[k!\binom{j}{k} - \sum_{i=0}^{k-1}(-1)^{i+k}{k\brack i} j^i\right]\\ &=k!\sum_{j=0}^n\binom{j}{k} - \sum_{i=0}^{k-1}(-1)^{i+k}{k\brack i}\sum_{j=0}^n j^i \end{align*} \]

上指标求和：

\[ S_n(k) = \frac{\prod_{i=n-k+1}^{n+1} i}{k+1}-\sum_{i=0}^{k-1}(-1)^{i+k}{k\brack i}S_i(n) \]

预处理 \(O(k^2)\)，询问 \(O(k^2)\)。

但是不用除法。

第二类 Stirling 数

考虑这样一个式子：

\[ i^k = \sum\limits_{j=0}^k \begin{Bmatrix}k\\j\end{Bmatrix}\dbinom{i}{j}j! \]

证明

\(i^k\) 可以看成将 \(k\) 个互不相同的球放进 \(i\) 个互不相同的盒子里。

那么枚举现在有 \(j\) 个非空的盒子，自然乘上 \(\begin{Bmatrix}k\\j\end{Bmatrix}\dbinom{i}{j}\)，因为这样是无序的，所以乘上 \(j!\) 才是有序的。

考虑求 \(S_k(n)=\sum_{i=1}^n i^k\)，即为：

\[ \begin{align*} &\sum_{i=1}^n \sum\limits_{j=0}^k \begin{Bmatrix}k\\j\end{Bmatrix}\dbinom{i}{j}j!\\ =&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits_{i=1}^n\dbinom{i}{j} \\ =&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\binom{n+1}{j+1}\\ =&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\dfrac{(n+1)!}{(j+1)(n-j)!}\\ =&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\dfrac{\prod_{i=n-j+1}^{n+1}i}{(j+1)} \end{align*} \]

预处理斯特林数，还要注意 \(j+1\) 在 \(P\) 下不一定存在逆元，但分子的某个数一定可以整除它。

预处理 \(O(k^2)\)，询问 \(O(k)\)。

也不用除法。