前置知识：
- 第二类斯特林数（Stirling Number）\(\begin{Bmatrix}n\\k\end{Bmatrix}\) 或 \(S(n,k)\) 表示将 \(n\) 个元素划分为 \(k\) 个互不区分的非空子集的方案数。
- 递推式：\(S(n,k) = S(n-1,k-1) + k \times S(n-1,k)\)，其中 \(S(n,0)=[n=0]\)。
贝尔数 \(B_n\) 表示 \(n\) 个元素被划分为若干个互不区分的非空子集的方案数（注意 \(B_0 = 1\)）。
显然 \(B_n = \sum\limits_{k=0}^{n}{S(n,k)}\) 就是求同一行第二类斯特林数的和，luogu - P5395 第二类斯特林数·行。
还有递推式 \(B_{n+1} = \sum\limits_{k=0}^{n}{\dbinom{n}{k}B_k}\)（考虑 \(a_{n+1}\) 和哪些元素一个集合）
打表代码
#include <bits/stdc++.h>using namespace std;
using LL = __int128_t;const LL mod = LL(1e18) + 3;void write(LL x){ if(x > 9) write(x / 10); putchar(x % 10 + '0'); }LL qpow(LL A, LL B){LL ret = 1;while(B > 0){if(B & 1) ret = ret * A % mod;A = A * A % mod, B >>= 1;}return ret;
}LL fac[1003], ifac[1003], B[1003];
LL C(int A, int B){ return fac[B] * ifac[A] % mod * ifac[B - A] % mod; }int main(){ios::sync_with_stdio(0), cin.tie(0);fac[0] = ifac[0] = 1;for(int i = 1; i <= 1000; i++) fac[i] = fac[i - 1] * i % mod, ifac[i] = qpow(fac[i], mod - 2);B[0] = 1;for(int n = 1; n <= 15; n++){B[n] = 0;for(int k = 0; k <= n - 1; k++) B[n] = (B[n] + C(k, n - 1) * B[k]) % mod;write(n), putchar(' '), write(B[n]), putchar('\n');}return 0;
}
表：
1: 1
2: 2
3: 5
4: 15
5: 52
6: 203
7: 877
8: 4,140
9: 21,147
10: 115,975
11: 678,570
12: 4,213,597
13: 27,644,437
14: 190,899,322
15: 1,382,958,545
这玩意就用来分析时间复杂度的，在 代码源 2025 CSP-S 模拟赛 Day13 - D题 蝴蝶图 & QOJ - #913. 蝴蝶图 中用到了（\(B_{11} = 678,570\)）。