自然数幂和

伯努利数

伯努利数是一个这样的数列:$\{1,-\frac{1}{2},\frac{1}{6},0,-\frac{1}{30},0,\frac{1}{42},0,-\frac{1}{30},0,\dots\}$

(所有大于$2$的奇数项都是$0$)

满足:

$$\begin{aligned} \sum_{k=0}^n \binom{n+1}{k} B_k = 0 \quad (n>0) \end{aligned}$$

换个方式写:

$$\begin{aligned} \sum_{k=0}^n \binom{n}{k} B_k &= B_n \quad (n\neq 1) \end{aligned}$$

观察上面的式子, 我们可以将$\{B_i\}$的EGF和$\{1,1,1,\dots\}$的EGF乘起来, 得到:

$$\begin{aligned} B(x) e^x &= B(x) + x \\ B(x) &= \frac{x}{e^x - 1} \end{aligned}$$

(左边加的$x$是特殊处理$n\neq 1$的限制)

所以我们就可以用多项式求逆在$O(n\log n)$的时间内求出$B_1\dots B_n$了.

设$S_m(n) = \sum_{i=0}^{n-1} i^m$, 那么有:

$$S_m(n) = \frac{1}{m+1} \sum_{k=0}^m \binom{m+1}{k}B_k n^{m+1-k}$$

---

递推

由$(i+1)^{k+1}-i^{k+1}=\sum\limits_{j=0}^k\binom{k+1}{j}i^j$累加得：

$$\begin{align*} (n+1)^{k+1}-1&=\sum_{i=1}^n\sum_{j=0}^k \binom{k+1}{j}i^j\\ &=\sum_{j=0}^k\binom{k+1}{j}\sum_{i=1}^n i^j \end{align*}$$

将$\sum\limits_{i=1}^{n}i^k$拿出来：

$$\begin{align*} \sum_{i=1}^n i^k &= \frac{(n+1)^{k+1}-1-\sum_{j=0}^{k-1}\binom{k+1}{j}\sum_{i=1}^n i ^ j}{\binom{k+1}{k}}\\ &= \frac{(n+1)^{k+1}-1-\sum_{j=0}^{k-1}\binom{k+1}{j}\color{red}{\sum_{i=1}^n i ^j}}{k+1} \end{align*}$$

直接递推即可。

---

差分

我们记一个序列的$k$次差分后的序列为$\Delta_k$

任何$k$次多项式的点值经过$k+1$次差分后都会变成全为$0$的序列，即$\Delta_k$均为$0$

我们对$f(n)=n^k$进行差分，设$c_k$为第$0$条对角线的第$k$项，那么有$f(n)=\sum\limits_{i=0}^k c_i \binom{n}{i}$。
所以：

$$\begin{align*} \sum_{i=0}^n f(i) &= \sum_{i=0}^n\sum_{j=0}^{k} c_j \binom{i}{j}\\ &= \sum_{j=0}^k c_j \sum_{i=0}^n \binom{i}{j}\\ &= \sum_{j=0}^k c_j \binom{n+1}{j+1} \end{align*}$$

关于最后那个组合数的推导$\sum_{i=0}^n \binom{i}{j}=\binom{n+1}{j+1}$，可以理解为：有$j+1$个球和$n+1$个盒子，枚举最后一个球放的位置$i+1$，剩下的球放置的方案就是$\binom{i}{j}$。

---

拉格朗日插值

可以证明$\sum\limits_{i=0}^n i^k$是一个$k+1$次多项式，因此我们可以用插值来做。
先求出$x=0\dots k+1$的点值，然后将$n$带入即可。
时间复杂度是$O(k\log k)$。

简便实现：
设多项式为$\sum_{i=0}^{k+1}coef_i(x) x^i$，根据拉格朗日插值的那个式子得到：

$$coef_{p+1}(x)=coef_p(x)\times \frac{(x-p)(p-k)}{(x-p-1)(p+1)}$$

直接将得到的系数乘点值即可。

如果要做到$O(k)$，线性筛得到$x^k$即可(瓶颈在于快速幂, 质数个数的级别是$\frac{k}{\log k}$的, 只对质数做快速幂, 时间复杂度就是$O(k)$的了)。

---

斯特林数

$$\begin{aligned} \binom{n}{k} = \frac{n^{\underline{k}}}{k!} = \frac{\sum\limits_{i = 0}^{k} \left[\begin{matrix} k \\ i \end{matrix}\right] (-1)^{k - i} n^i}{k!} \\ k! \binom{n}{k} = \sum_{i = 0}^{k} \left[\begin{matrix} k \\ i \end{matrix}\right] (-1)^{k - i} n^i \\ \\ n^k = k! \binom{n}{k} - \sum_{i = 0}^{\color{red}{k - 1}} \left[\begin{matrix} k \\ i \end{matrix}\right] (-1)^{k - i} n^i \end{aligned}$$

那么

$$\begin{aligned} \sum_{i = 0}^{n} i^k &= \sum_{i = 0}^{n} \left( k! \binom{i}{k} - \sum_{j = 0}^{k - 1} \left[\begin{matrix} k \\ j \end{matrix}\right] (-1)^{k - j} i^j \right) \\ &= k! \sum_{i = 0}^{n} \binom{i}{k} - \sum_{i = 0}^{n} \sum_{j = 0}^{k - 1} \left[\begin{matrix} k \\ j \end{matrix}\right] (-1)^{k - j} i^j \\ &= k! \binom{n + 1}{k + 1} - \sum_{j = 0}^{k - 1} \left[\begin{matrix} k \\ j \end{matrix}\right] (-1)^{k - j} \color{red}{\sum_{i = 0}^{n} i^j} \\ &= \frac{(n + 1)^{\underline{k + 1}}}{k + 1} - \sum_{j = 0}^{k - 1} \left[\begin{matrix} k \\ j \end{matrix}\right] (-1)^{k - j} \color{red}{\sum_{i = 0}^{n} i^j} \end{aligned}$$

至于$\displaystyle\frac{1}{k+1}$，一定可以在$(n+1)^{\underline{k+1}}$中除去。

所以直接$O(k^2)$预处理出第一类斯特林数即可。