这道题目结合了你提供的Bell数递推公式以及基础的组合数学和 动态规划（DP） 知识。

这符合 GESP 4-6 级（大致对应 NOIP 普及组）考察的重点：递推关系、数组应用、以及对组合数的理解。

题目名称：集合分组方案 (Partition)

题目背景

在组合数学中，集合 $S$ 的一个分拆是指将 $S$ 划分为若干个互不相交的非空子集，这些子集的并集等于 $S$。例如，集合 $\{1, 2, 3\}$ 有 5 种不同的分拆方式：

1. $\{\{1, 2, 3\}\}$
2. $\{\{1, 2\}, \{3\}\}$
3. $\{\{1, 3\}, \{2\}\}$
4. $\{\{2, 3\}, \{1\}\}$
5. $\{\{1\}, \{2\}, \{3\}\}$

可能的分拆方案的总数被称为 Bell 数（贝尔数），记作 $B_n$。

题目描述

给定一个正整数 $n$，请你计算含有 $n$ 个不同元素的集合共有多少种分拆方案。 已知 Bell 数满足以下递推公式：

其中，$B_0 = 1$，$\binom{n}{k}$ 是组合数，表示从 $n$ 个元素中选出 $k$ 个元素的方案数。

由于结果可能非常大，请输出结果对 $10^9 + 7$ 取模后的值。

输入格式

输入一行，包含一个正整数 $n$。

输出格式

输出一个整数，表示 $B_n \pmod{10^9 + 7}$ 的值。

样例输入

3

样例输出

5

数据范围

• 对于 60% 的数据：$1 \le n \le 20$
• 对于 100% 的数据：$1 \le n \le 1000$

解题思路（针对 GESP/NOIP 选手）

1. 理解公式： 题目直接给出了递推式。要计算 $B_n$，我们需要先算出 $B_0, B_1, \dots, B_{n-1}$。这是一个典型的动态规划（递推）过程。

2. 处理组合数 $\binom{n}{k}$： 由于 $n$ 达到 1000，直接计算阶乘会溢出。我们需要利用 杨辉三角（Pascal's Triangle） （预先计算，保存结果用于后续查表）：

   $$C(i, j) = C(i-1, j-1) + C(i-1, j)$$

   所有的计算都要在过程中对 $10^9+7$ 取模。

3. 算法流程：

   • 第一步：使用二维数组 C[1005][1005] 预处理出 1000 以内的组合数。
   • 第二步：定义一维数组 B[1005]，初始化 B[0] = 1。
   • 第三步：外层循环 $i$ 从 0 到 $n-1$，内层循环 $k$ 从 0 到 $i$，按照公式 $B_{i+1} = \sum \binom{i}{k} B_k$ 计算。
   • 复杂度：预处理 $O(n^2)$，递推 $O(n^2)$，总时间复杂度 $O(n^2)$，对于 $n=1000$ 绰绰有余。

核心代码参考 (C++)

#include <iostream>
#include <vector>

using namespace std;

long long C[1005][1005];
long long B[1005];
const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;

    // 1. 预处理组合数 (杨辉三角)
    for (int i = 0; i <= n; i++) {
       /// 见详解
    }

    // 2. 递推计算 Bell 数
    B[0] = 1;
    for (int i = 0; i < n; i++) {
        // 计算 B[i+1] = sum_{k=0}^{i} C(i, k) * B[k]
        //见详解
    }

    cout << B[n] << endl;

    return 0;
}

难度评价

• GESP 4级：考察循环和基本数组操作（若 $n$ 较小）。
• GESP 5级：考察组合数递推和基本的取模运算。
• GESP 6级/NOIP 普及组：考察对数学定义的程序化建模以及 $O(n^2)$ 的动态规划优化。