定义：定义贝尔数 B_n 为：n 个元素划分为任意个集合的方案数。由第二类斯特林数定义可得：

B_n=\sum_{i=0}^{n}\begin{Bmatrix}n\cr i\end{Bmatrix}

递推式：

B_{n+1}=\sum_{i=0}^{n}\binom{n}{i}B_i

由此可以 O(n^2) 递推；

Touchard 同余：

贝尔数满足 Touchard 同余，即：

B_{n+p}=(B_{n}+B_{n+1})\bmod p\ (p\in prime)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 50;
const int M = 1e3 + 10;
int n, P;

int C[M][M], f[N];
void init() {
    for (int i = 0; i < M; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
    }
    memset(f, 0, sizeof(f));
    f[0] = f[1] = 1;
    for (int i = 2; i < M; i++) {
        for (int j = 0; j < i; j++) {
            (f[i] += C[i - 1][j] * f[j]) %= P;
        }
    }
}

int Bell(int n, int p) {
    if (n < 0) return 0;
    if (f[n]) return f[n];
    return f[n] = (Bell(n - p, p) + Bell(n - p + 1, p)) % p;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &P);
        init();
        printf("%d\n", Bell(n, P));
    }
    return 0;
}

也可以构造矩阵递推：

\begin{bmatrix}
0&0&0&0&0&\cdots& 0&0 &1\cr
1&1&0&0&0&\cdots& 0&0&0\cr
0&1&1&0&0&\cdots& 0&0&0\cr
0&0&1&1&0&\cdots& 0&0&0\cr
0&0&0&1&1&\cdots& 0&0&0\cr
\cdots&\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cr
0&0&0&0&0&\cdots&1&1&0\cr
0&0&0&0&0&\cdots&0&1&1\cr
\end{bmatrix} \cdot
\begin{bmatrix}
B[0]\cr B[1]\cr B[2]\cr B[3]\cr B[4]\cr \cdots\cr B[p-2]\cr B[p-1]
\end{bmatrix} =
\begin{bmatrix}
B[p-1]\cr B[p+0]\cr B[p+1]\cr B[p+2]\cr B[p+3]\cr \cdots\cr B[2p-3]\cr B[2p-2]
\end{bmatrix}

指数型生成函数

P5748 集合划分计数

B(x)=e^{e^x-1}

VI Bell(int n) {
    VI fac(n + 1), ifac(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % P;
    ifac[n] = inv(fac[n]);
    for (int i = n; i; i--) ifac[i - 1] = 1LL * ifac[i] * i % P;
    ifac[0] = 0;
    VI ret = exponent(ifac);
    for (int i = 1; i <= n; i++) ret[i] = 1LL * ret[i] * fac[i] % P;
    return ret;
}

int main()
{
    VI ans = Bell(100000);
    int ; scanf("%d", &);
    while ($--) {
        int n; scanf("%d", &n);
        printf("%d\n", ans[n]);
    }
    return 0;
}