集合的划分

题目描述

把 $n$ 个互不相同的元素划分成 $k$ 个非空互不相交的子集，求划分数 $S(n,k)$ （ $0<k\leqslant n<30$ ）。输入一行 $n,k$ ，输出 $S(n,k)$ 。样例：输入 10 6 输出 22827。

思路

按第 $n$ 个元素去向分：单独成盒 $S(n-1,k-1)$ 种，或放入已有 $k$ 盒之一共 $k\cdot S(n-1,k)$ 种，得递推 $S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)$ ；用一维数组逆序滚动在 $O(n\cdot k)$ 内求出答案。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-30 04:41
# update_at: 2026-09-30 04:45

import sys

MASK = (1 << 64) - 1
HALF = 1 << 63


def to_ll(x: int) -> int:
    """把整数截成 64 位有符号 long long，与 std.cpp 溢出行为一致。"""
    x &= MASK
    return x - (1 << 64) if x >= HALF else x


def stirling2(n: int, k: int) -> int:
    """第二类 Stirling 数 S(n,k)：n 个不同元素划分成 k 个非空无标号集合的方案数。"""
    if k == 0 or k > n:
        return 0

    dp = [0] * (k + 2)
    dp[1] = 1  # S(1, 1) = 1

    for i in range(2, n + 1):
        upper = min(i, k)
        # 从大到小更新，避免覆盖上一行的状态。
        for j in range(upper, 0, -1):
            single = 1 if j == i else dp[j - 1]        # 第 i 个元素单独成一盒
            new_alone = 1 if j == 1 else dp[j]         # 第 i 个元素放进已有的某一盒
            dp[j] = to_ll(single + to_ll(j * new_alone))

    return dp[k]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k = next(data), next(data)
    print(stirling2(n, k))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
48
49/**
 * 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-10-04 13:25
 * update_at: 2026-10-04 13:25
 */

#include <iostream>
using namespace std;

typedef long long ll;

// n 个不同元素划分成 k 个非空无标号集合的方案数 = 第二类 Stirling 数 S(n,k)
// 递推：S(n,k) = S(n-1,k-1) + k * S(n-1,k)
// 边界：S(i,1)=1, S(i,i)=1, S(i,j)=0(>= i 越界或 j==0)
// 用一维数组滚动：外层 i 从 2..n，内层 j 从大到小更新，保留上一行 S(i-1,j-1) 的值。
const int MAXN = 35;
ll dp[MAXN];

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

    ll n, k;
    cin >> n >> k;

    if (k == 0 || k > n) {
        cout << 0 << "\n";
        return 0;
    }

    // 初值 S(1,1)=1
    dp[1] = 1;
    for (ll j = 2; j <= k; j++) dp[j] = 0;

    for (ll i = 2; i <= n; i++) {
        ll upper = min(i, k);
        // j 从大到小：dp[j-1] 仍是上一行 S(i-1,j-1) 的值
        for (ll j = upper; j >= 1; j--) {
            ll single = (j == i) ? 1 : dp[j - 1];   // 第 i 个元素单独成一盒
            ll into_old = (j == 1) ? 1 : dp[j];     // 第 i 个元素放进已有的某一盒
            dp[j] = single + j * into_old;          // 按 64 位有符号 long long 自然溢出
        }
    }

    cout << dp[k] << "\n";
    return 0;
}

目录

题目描述

思路

参考代码