## 丧钟为谁而鸣（bell）解析

#### 算法 1 $\Theta(n^2)$

不难得到递推式
$$
B_{n+1}=\sum_k \binom{n}{k}B_k
$$

#### 算法 2 $\Theta(n\log n)$（迫真）

不难得到 Bell 数的 EGF 为 $\newcommand{\me}{\mathrm{e}}\me^{\me^x-1}$。

实现二项 $\exp$ 即可。但是本算法具有<font size=10>很大</font>的常数。

#### 算法 3 $\Theta(n)$ for $\bmod p$

Bell 数满足性质 $B_{n+p}\equiv B_{n+1}+B_n \pmod p$，于是算出前 $p$ 项后递推即可。

由于这个性质可以在 Wikipedia 上查到，所以没给很多分。正解的推导可以直接说明这为什么是对的。

#### 算法 4 for small $p^k$

打表会发现这个时候数列有一个不大的周期。

#### 算法 5 $\Theta(npk)$

你猜数列总是个线性递推？这其实也是对的，或许你可以通过 Reeds-Sloane（模合数 BM）来跑出这个递推式。它的量级大概是 $pk$ 级别。

#### 算法 6 $\Theta(n(p+k))$

让我们来考虑一下 $B(x)=\me^{\me^x-1}$ 这个生成函数。我们对两边求导，可以得到
$$
B'(x)=B(x)\me^x
$$
考察它的系数，这就对应于算法 1 的恒等式，接下来考虑再求导
$$
\begin{aligned}
B''(x)&=B'(x)\me^x+B(x)\me^x\\
&=B(x)\me^{2x}+B'(x)\\
B''(x)-B'(x)&=B(x)\me^{2x}
\end{aligned}
$$
注意到这个式子一直做下去会得到如下等式：
$$
\sum_{k=1}^p f_kB^{(k)}(x) = B(x)\me^{px}
$$
提取第 $n$ 次项系数，就建立了递推式
$$
\sum_{k=1}^p f_kB_{n+k} = \sum_{k\ge 0} \binom n k B_{n-k} p^k
$$
而 $p^k$ 很快就被 $\bmod$ 掉了，因此这个递推式有用的项只有 $p+k$ 项。

左边的系数不难计算，设 $B(x)\me^{kx}=F_k(\mathrm{D})B(x)$，可得
$$
\begin{aligned}
(B(x)\me^{kx})'&=\mathrm{D}F_k(\mathrm{D})B(x)\\
B(x)\me^{(k+1)x}+kB(x)\me^{kx}&=\mathrm{D}F_k(\mathrm{D})B(x)\\
B(x)\me^{(k+1)x}&=(\mathrm{D}F_k(\mathrm{D})-kF_k(\mathrm{D}))B(x)\\
F_{k+1}(x)&=(x-k)F_k(x)\\
F_k(x) &= x(x-1)\cdots (x-k+1)
\end{aligned}
$$