1303 集合的划分
1303 集合的划分
【算法】 递推、数学、第二类斯特林数
【C++】 二维数组、unsigned long long、函数
【难度】 普及−
一、题目简述
设 是含有 个元素的集合,将其划分成 个满足以下条件的子集合:
- 每个子集非空
- 任意两个子集的交集为空(互不相交)
- 所有子集的并集等于
也就是把 个不同的元素放入 个无区别的盒子,每个盒子至少一个元素。求有多少种放法。记作 。
| 数据范围 | 说明 |
|---|---|
| 输入两个整数 和 |
输入:一行两个整数 和 。
输出:一个整数 。
样例:
输入:10 6
输出:22827二、解题思路
2.1 问题本质
这道题求的是第二类斯特林数(Stirling numbers of the second kind),记作 或 。
它表示:将 个有区别的元素划分成 个无区别的非空子集的方案数。
对比理解:盒子无区别,意味着只要看"元素和谁在一组",不关心组的编号。
2.2 递推公式推导
思考第 个元素 的去向,只有两种可能:
情况一: 单独成一个子集
剩下 个元素要分成 个子集 → 方案数 。
情况二: 加入已有的某个子集
先把前 个元素分成 个子集 → 方案数 。然后 可以加入这 个子集中的任意一个 → 乘上 。
所以总方案数:。
综合:
2.3 边界条件
| 条件 | 值 | 含义 |
|---|---|---|
| 所有人挤一个集合,只有一种 | ||
| 每人单独一个集合,只有一种 | ||
| 子集数比元素多,不可能 | ||
| (且 ) | 0 个子集无法覆盖元素 |
2.4 递归思路
递推公式本身就是递归定义的,把大问题不断拆成更小的子问题:
S(4, 2) // 原问题
├── S(3, 1) = 1 // a4 单独一组
└── 2 × S(3, 2) // a4 加入已有组
├── S(2, 1) = 1 // a3 单独一组
└── 2 × S(2, 2) = 2 × 1 = 2 // a3 加入已有组每次递归都问同一个问题:最后一个元素是单独成组,还是加入已有组? 一直问到边界条件( 或 )返回答案。
这其实就是一棵递归树,每条从根到叶子的路径对应一种划分方式。
递归 vs 递推:递归是自顶向下(从大问题拆到边界),递推是自底向上(从边界填表到大问题)。两种写法本质相同,思路互补。
2.5 手动模拟样例
以 为例,验证递推:
| 计算过程 | 结果 | |
|---|---|---|
| 边界 | 1 | |
| 边界 | 1 | |
| 边界 | 1 | |
| 边界 | 1 | |
| 3 | ||
| 边界 | 1 | |
| 7 |
可以手动验证:4 个元素 分成 2 个非空子集:
{a} {b,c,d} {b} {a,c,d} {c} {a,b,d} {d} {a,b,c}
{a,b} {c,d} {a,c} {b,d} {a,d} {b,c}正好 7 种 ✓
2.6 数据范围分析
, 的值增长很快。用 unsigned long long(最大约 )可以覆盖题目要求的范围。可以开一个 S[35][35] 的二维数组做递推。
三、参考代码
3.1 递归写法(自顶向下)
将递推公式直接翻译成递归函数,配合一个记忆化数组避免重复计算:
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
unsigned long long memo[N][N]; // 记忆化:-1 表示未计算
// 返回 S(n, k):将 n 个元素分成 k 个非空子集的方案数
unsigned long long S(int n, int k) {
// 先查记忆化表(已算过直接返回)
if (memo[n][k] != (unsigned long long)-1)
return memo[n][k];
// 边界条件
if (k == 1 || k == n)
return memo[n][k] = 1;
if (k == 0 || k > n)
return memo[n][k] = 0;
// 递推公式:第 n 个元素单独一组 + 加入已有组
return memo[n][k] = S(n - 1, k - 1) + k * S(n - 1, k);
}
int main() {
// 初始化记忆化表为 -1
memset(memo, -1, sizeof(memo));
int n, k;
cin >> n >> k;
cout << S(n, k) << endl;
return 0;
}关键点:
memo[n][k]记忆化数组记录已算过的值,每个状态只算一次,避免递归爆炸。memset(memo, -1, sizeof(memo))把整个数组的每个字节都设成0xFF,对unsigned long long来说就是最大值,用来标记"尚未计算"。- 递归函数 先查表、再判边界、最后用递推公式递推,逻辑和图解完全一致。
3.2 递推写法(自底向上)
从边界开始逐步填表,直到算出目标值:
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
unsigned long long S[N][N]; // S[n][k]:第二类斯特林数
int main() {
int n, k;
cin >> n >> k;
// 边界条件
for (int i = 1; i <= n; i++) {
S[i][1] = 1; // 分成 1 个子集,只有一种
S[i][i] = 1; // 分成 i 个子集(每人一个),只有一种
}
// 递推填表
for (int i = 3; i <= n; i++) {
for (int j = 2; j < i; j++) {
S[i][j] = S[i-1][j-1] + j * S[i-1][j];
}
}
cout << S[n][k] << endl;
return 0;
}说明:
- 用
unsigned long long防止溢出(普通int远远不够)。- 外层从 开始,因为 的情况已被边界覆盖。
- 内层 从 到 ,跳过边界已有的 和 。
3.3 两种写法对比
| 递归 + 记忆化 | 递推填表 | |
|---|---|---|
| 方向 | 自顶向下(大→小) | 自底向上(小→大) |
| 代码长度 | 稍短,贴近公式 | 稍长,但结构清晰 |
| 思维 | 直接照着递推公式翻译 | 需要设计填表顺序 |
| 额外开销 | 函数调用栈 | 无 |
| 适合场景 | 递推公式明确的入门题 | 需严格控制内存 / 速度的题 |
两种都会就是最好的。本题 ,两种写法都能轻松通过。
四、复杂度分析
| 递归 + 记忆化 | 递推填表 | |
|---|---|---|
| 时间复杂度 | ||
| 空间复杂度 |
两种写法的时间、空间复杂度完全相同:
- 每个 状态最多被计算一次(递归由 memo 保证,递推由循环保证)。
- 状态总数约为 个,每个状态 计算。
- 递归写法多了一个函数调用栈的开销,最深 层,对本题影响很小。
由于 ,无论哪种写法都飞快。
五、知识扩展
5.1 第一类 vs 第二类斯特林数
| 第一类(无符号) | 第二类 | |
|---|---|---|
| 符号 | 或 | 或 |
| 含义 | 个元素分成 个圆排列 | 个元素分成 个子集 |
| 递推 |
区别在于系数:第一类乘 ,第二类乘 。
5.2 贝尔数(Bell Number)
把所有可能的 值对应的斯特林数加起来,得到的是贝尔数 :
它表示:把 个元素分成任意数量非空子集的方案总数。。
5.3 对比"放球模型"
| 球(元素) | 盒(子集) | 盒可空? | 计数 | 对应 |
|---|---|---|---|---|
| 不同 | 不同 | 不可空 | 先划分再给盒子编号 | |
| 不同 | 相同 | 不可空 | 本题 | |
| 不同 | 不同 | 可空 | 每个元素独立选盒子 | |
| 不同 | 相同 | 可空 | 枚举非空盒数 |
六、易错点
- 忘记用
unsigned long long: 接近 30 时结果远超int范围(约 )。 - 边界初始化遗漏: 和 缺一不可。
- 循环范围写错:内层 要小于 ,不是小于等于 。
- 递推公式写错:系数是 (当前子集数),不是 或 。
- 递归写法忘记记忆化:单纯递归会导致大量重复计算, 时直接爆炸。必须用
memo[][]保存中间结果。 memset(memo, -1, sizeof(memo))误用:这句只能将每个字节设为0xFF,对unsigned long long刚好是全 1(即最大值),可以充当"未计算"标记。换成别的类型(如int+ 想用-1之外的值)就不能简单 memset 了。
