针对 Bell数（贝尔数） 的计算，根据题目要求的 $n$ 的规模，解法可以从最朴素的递归演进到最高效的线性递推（贝尔三角形）。

以下是针对 NOIP C++14 标准的三个版本：

版本 1：暴力递归版（适合 $n \le 12$）

思路分析： 直接根据公式 $B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k$ 编写递归函数。组合数 $\binom{n}{k}$ 也采用递归计算。 缺点： 存在大量重复计算，时间复杂度呈指数级增长。

#include <iostream>

using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

// 递归计算组合数 C(n, k)
ll C(int n, int k) {
    if (k == 0 || k == n) return 1;
    if (k > n) return 0;
    return (C(n - 1, k - 1) + C(n - 1, k)) % MOD;
}

// 暴力递归计算 Bell 数
ll solve_B(int n) {
    if (n == 0) return 1;
    ll res = 0;
    // 根据公式: B_n = sum_{k=0}^{n-1} C(n-1, k) * B_k
    for (int k = 0; k < n; k++) {
        res = (res + C(n - 1, k) * solve_B(k)) % MOD;
    }
    return res;
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    cout << solve_B(n) << endl;
    return 0;
}

• 时间复杂度： $O(2^n)$，计算 $B_{15}$ 就会明显变慢。
• 空间复杂度： $O(n)$，主要是递归栈的深度。

版本 2：动态规划 + 杨辉三角预处理（标准 $O(n^2)$ 版，适合 $n \le 1000$）

思路分析： 在 GESP 5-6 级中，最稳妥的方法是使用 DP（动态规划）。

1. 使用二维数组预处理杨辉三角，求出所有 $\binom{n}{k}$。
2. 使用一维数组记录 $B_k$，避免重复递归。

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 1005;

ll c[MAXN][MAXN];
ll b[MAXN];

int main() {
    int n;
    if (!(cin >> n)) return 0;

    // 1. 预处理组合数: O(n^2)
    for (int i = 0; i <= n; i++) {
        c[i][0] = 1; // 易错点：不要忘记初始化每行的首项为1
        for (int j = 1; j <= i; j++) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
        }
    }

    // 2. DP 计算 Bell 数: O(n^2)
    b[0] = 1;
    for (int i = 0; i < n; i++) {
        ll sum = 0;
        for (int k = 0; k <= i; k++) {
            // 核心公式: B_{i+1} = sum(C(i, k) * B_k)
            // 易错点：相乘时务必先转 long long 防止溢出，再取模
            sum = (sum + c[i][k] * b[k]) % MOD;
        }
        b[i + 1] = sum;
    }

    cout << b[n] << endl;
    return 0;
}

• 时间复杂度： $O(n^2)$。对于 $n=1000$，$10^6$ 次运算，在 1s 内轻松跑完。
• 空间复杂度： $O(n^2)$，主要消耗在组合数数组 c[1005][1005]。

版本 3：最优复杂度：贝尔三角形（Bell Triangle）

思路分析： 类似于杨辉三角，贝尔数也有一个构造三角形：

1. 第一行第一个数是 $B_0=1$。
2. 每一行第一个数等于上一行最后一个数。
3. 每一个数等于它左边和左上角的数之和。 优势： 不需要计算繁琐的组合数，只有加法运算，且空间可以优化到 $O(n)$。

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    if (n == 0) {
        cout << 1 << endl;
        return 0;
    }

    // tri[i] 滚动存储当前行的值，优化空间复杂度到 O(n)
    vector<ll> tri(n + 1);
    
    tri[0] = 1; // 相当于 B_0
    
    for (int i = 1; i <= n; i++) {
        // 规则：当前行第一个数 = 上一列最后一个数
        ll prev_last = tri[i - 1]; 
        ll left_val = prev_last;
        
        // 易错点：为了实现空间滚动，我们需要从前往后更新
        // 但为了不覆盖掉上一行需要用到的数据，这里用 temp 暂存
        // 实际上贝尔三角形用二维数组写最稳，这里展示空间优化写法
        vector<ll> next_row(i + 1);
        next_row[0] = left_val;
        
        for (int j = 1; j <= i; j++) {
            // 规则：A[i][j] = A[i][j-1] + A[i-1][j-1]
            next_row[j] = (next_row[j - 1] + tri[j - 1]) % MOD;
        }
        tri = next_row;
    }

    // Bell(n) 是第 n 行的第 0 个元素（或者第 n-1 行的最后一个）
    // 按照本代码逻辑，n 行处理完后，第一个元素即为 B_n
    cout << tri[0] << endl;

    return 0;
}

• 时间复杂度： $O(n^2)$，但只有加法，常数极小。
• 空间复杂度： $O(n)$。

时间复杂度优化建议与思考过程

1. 思考过程：

• 从递归到 DP： 任何时候看到类似 $B_{n+1} = \sum \dots B_k$ 的形式，第一反应应该是“重叠子问题”，必须通过存储中间结果来消除重复计算。
• 从组合数到加法： 虽然 $O(n^2)$ 的组合数方案已经足够过 $n=1000$，但组合数涉及乘法和取模。贝尔三角形（也叫 Aitken's array）将乘法转化为加法，在 $n$ 极大或高精度计算时速度优势明显。

2. 进一步优化（进阶）：

• $O(n \log n)$ 方案： 如果 $n \le 10^5$，即使是贝尔三角形的 $O(n^2)$ 也会超时。此时需要使用多项式指数函数（NTT优化）。
  • Bell 数的指数生成函数为：$F(x) = \sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = e^{e^x - 1}$。
  • 利用分治 FFT 或牛顿迭代法求多项式 exp，可以在 $O(n \log n)$ 时间内求出 $B_1 \dots B_n$。
• 模数问题： 如果题目模数不是质数（如 $10^6$），则不能用逆元求 $n!$。此时必须回归 $O(n^2)$ 的贝尔三角形方案，因为它只涉及加法，不依赖模数性质。

3. 易错总结：

• 溢出： 计算 C[i][k] * B[k] 时，即使两者都取过模，乘积也可能达到 $10^{18}$ 级别，必须使用 long long。
• 边界： $B_0 = 1$ 是很多推导的基石，代码初始化时务必注意。
• 取模： 所有的加法后面都要跟 % MOD，防止在累加循环中溢出。