龙兄摘苹果

题意

有 n 个互不相同的苹果和 k 个篮子。

要求把所有苹果放进篮子里，并且每个篮子都不能为空。问一共有多少种放法，最后输出答案对 p 取模后的结果。

思路

先看一个最朴素的理解方式：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-09 09:44
 * update_at: 2026-07-09 09:47
 */
// brute.cpp：暴力枚举每个苹果放进哪个篮子，只适合很小的数据。
#include <bits/stdc++.h>
using namespace std;

int n, k;
long long p;
long long ans;

void dfs(int idx, int used) {
    if (idx > n) {
        if (used == k) {
            ans++;
        }
        return;
    }

    // 放进已经开好的某一个篮子。
    for (int i = 1; i <= used; i++) {
        dfs(idx + 1, used);
    }

    // 开一个新篮子给当前苹果。
    if (used < k) {
        dfs(idx + 1, used + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k >> p;

    ans = 0;
    dfs(1, 0);

    cout << ans % p << '\n';
    return 0;
}

brute.cpp 按苹果编号从小到大 DFS：

当前苹果放进某个已经开的篮子
或者开一个新篮子给它

这样可以完整枚举所有方案，适合作为小数据对拍程序。

但正式数据里 n 最多到 10000，显然不能暴力。

设：

dp[i][j] 表示前 i 个苹果恰好放进 j 个非空篮子的方案数

考虑第 i 个苹果，有两种放法：

单独开一个新篮子
那前 i-1 个苹果必须已经放成 j-1 个非空篮子
贡献：dp[i-1][j-1]
放进已有的某个旧篮子
前 i-1 个苹果已经放成 j 个非空篮子
现在有 j 个旧篮子可选
贡献：j * dp[i-1][j]

所以转移式就是：

dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j]

样例转移表

以样例 n = 4, k = 2 为例，部分状态如下：

`i \\ j`	0	1	2
0	1	0	0
1	0	1	0
2	0	1	1
3	0	1	3
4	0	1	7

最后 dp[4][2] = 7，对 3 取模后得到 1。

DP 公式

设 $dp_{i,j}$ 表示前 $i$ 个苹果恰好放进 $j$ 个非空篮子的方案数。第 $i$ 个苹果有两种去处：新开一个篮子，或放进已有的 $j$ 个篮子之一。因此：

dp_{i,j}=dp_{i-1,j-1}+j\cdot dp_{i-1,j}

边界为：

dp_{0,0}=1

最终答案为：

dp_{n,k}\bmod p

因为每一层只依赖上一层，所以实现时可以用滚动数组把二维 DP 压成一维。

公式解释：放第 i 个苹果时，如果它单独开一个新篮子，就从 dp_{i-1,j-1} 来；如果放进已有篮子，则有 j 个篮子可选，所以贡献是 j * dp_{i-1,j}。

实现时要注意，p 可能超过 int 范围，读入和 DP 数组都应该使用 long long。计算 j * dp[j] 时中间乘法也可能超过 long long，所以代码里用 __int128 暂存后再取模。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-09 09:44
 * update_at: 2026-07-09 09:47
 */
// main.cpp：第二类斯特林数递推，滚动数组优化。
#include <bits/stdc++.h>
using namespace std;

const int MAXK = 1005;

int n, k;
long long p;
long long dp[MAXK];  // dp[j] 表示当前处理完若干苹果后，放成 j 个非空篮子的方案数。
long long ndp[MAXK]; // ndp[j] 表示下一层转移后的方案数。

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k >> p;

    dp[0] = 1 % p;

    for (int i = 1; i <= n; i++) {
        int upper = min(i, k);
        for (int j = 0; j <= upper; j++) {
            ndp[j] = 0;
        }

        for (int j = 1; j <= upper; j++) {
            // 第 i 个苹果单独开一个新篮子，或者放进已有的 j 个篮子之一。
            __int128 ways = dp[j - 1];
            ways += (__int128)j * dp[j];
            ndp[j] = (long long)(ways % p);
        }

        for (int j = 0; j <= upper; j++) {
            dp[j] = ndp[j];
        }
    }

    cout << dp[k] % p << '\n';
    return 0;
}

复杂度

时间复杂度： $O(nk)$
空间复杂度： $O(k)$

总结

这题的关键是按“最后加入的那个苹果”分类讨论。

只要看清楚它不是“开新篮子”，就是“进入已有篮子”，转移式就会自然写出来。这也是第二类斯特林数最经典的递推形式。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

样例转移表

DP 公式

代码

复杂度

总结

一图流解析