深入浅出学算法042-集合的划分

Question

深入浅出学算法042-集合的划分

时间限制 : 1.000 sec 内存限制 : 128 MB
使用C++/C语言完成
题目描述
设S是一个具有n个元素的集合，S＝｛a1，a2，……，an｝，现将S划分成k个满足下列条件的子集合S1，S2，……，Sk ，且满足：

则称S1，S2，……，Sk是集合S的一个划分。它相当于把S集合中的n个元素a1 ，a2，……，an 放入k个（0＜k≤n＜30）无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1 ，a2 ，……，an 放入k个无标号盒子中去的划分数S(n，k)对1e9+7取余之后的值。

输入
输入n,k
输出
输出S(n,k) mod 1e9+7 的值
样例输入 Copy
23 7
样例输出 Copy
968438818

Answer 1

让【宝码香车】来帮你解答，本回答参考DeepSeek编写，并整理提供，如果还有疑问可以点击头像关注私信或评论。

如果答案让您满意，请采纳、关注，非常感谢！

---

这个问题是关于集合划分的经典问题，通常被称为“第二类斯特林数”（Stirling numbers of the second kind）。第二类斯特林数 ( S(n, k) ) 表示将 ( n ) 个不同的元素划分成 ( k ) 个非空子集的方式数。

问题分析

我们需要计算 ( S(n, k) ) 并对结果取模 ( 10^9 + 7 )。第二类斯特林数可以通过递推公式来计算：

[ S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1) ]

其中：

• ( S(n-1, k) ) 表示将第 ( n ) 个元素放入已有的 ( k ) 个子集中。
• ( S(n-1, k-1) ) 表示将第 ( n ) 个元素单独作为一个新的子集。

边界条件：

• ( S(0, 0) = 1 )
• ( S(n, 0) = 0 ) 当 ( n > 0 )
• ( S(0, k) = 0 ) 当 ( k > 0 )

代码实现

我们可以使用动态规划来计算 ( S(n, k) )。以下是C++的实现代码：

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

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

    // 创建一个二维数组来存储S(n, k)
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));

    // 初始化边界条件
    dp[0][0] = 1;

    // 填充dp表
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            dp[i][j] = (j * dp[i-1][j] + dp[i-1][j-1]) % MOD;
        }
    }

    // 输出结果
    cout << dp[n][k] << endl;

    return 0;
}

代码解释

1. 初始化：我们创建一个二维数组 dp，其中 dp[i][j] 表示将 ( i ) 个元素划分成 ( j ) 个子集的方式数。
2. 边界条件：dp[0][0] = 1 表示将 0 个元素划分成 0 个子集的方式数为 1。
3. 递推关系：我们使用递推公式 dp[i][j] = (j * dp[i-1][j] + dp[i-1][j-1]) % MOD 来填充 dp 表。
4. 输出结果：最后输出 dp[n][k] 的值，即 ( S(n, k) ) 对 ( 10^9 + 7 ) 取模的结果。

样例输入输出

对于输入 23 7，程序将输出 968438818，这与题目中的样例输出一致。

复杂度分析

• 时间复杂度：( O(n \times k) )，因为我们需要填充一个 ( n \times k ) 的二维数组。
• 空间复杂度：( O(n \times k) )，用于存储 dp 表。

这个算法在给定的约束条件下（( n < 30 )）是非常高效的。