数的划分

题目描述

把整数 $n$ 分成 $k$ 份，每份不能为空，任意两份不能相同（不考虑顺序），例如 $n=7$ 、 $k=3$ 时 1,1,5、1,5,1、5,1,1 算同一种。输入一行两个整数 $n, k$ （ $6 < n \leqslant 200$ ， $2 \leqslant k \leqslant 6$ ），输出不同的分法总数。样例输入 7 3 对应输出 4：1,1,5；1,2,4；1,3,3；2,2,3。

思路

设 $f[i][j]$ 为把 $i$ 拆成 $j$ 个正整数、不计顺序的方案数，按最小值是否为 $1$ 分类：最小值为 $1$ 时删掉一个 $1$ 得 $f[i-1][j-1]$ ，最小值 $\geqslant 2$ 时每份减 $1$ 得 $f[i-j][j]$ ，两类不重不漏，故 $f[i][j] = f[i-1][j-1] + f[i-j][j]$ 。边界： $j=1$ 时只有 $1$ 种， $i<j$ 时为 $0$ ；状态 $O(nk)$ 、转移 $O(1)$ ，递推即可。

参考代码

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#!/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:05
# update_at: 2026-09-30 04:05

import sys
from functools import cache


@cache
def ways(total: int, parts: int) -> int:
    """把 total 分成 parts 个正整数、不计顺序的方案数。

    parts 份都要非空，所以 total < parts 无解；只剩一份时整块给它，只有 1 种。
    任何方案按「最小值是否为 1」二分：最小值是 1 → 拿掉这个 1，
    剩 ways(total-1, parts-1)；最小值 ≥ 2 → 每份先垫掉 1，整体减 parts，
    一一对应到 ways(total-parts, parts)。两类不重不漏。
    """
    if total < parts:
        return 0
    if parts == 1:
        return 1
    return ways(total - 1, parts - 1) + ways(total - parts, parts)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k = next(data), next(data)  # 题面只有一组数据，6 < n <= 200，2 <= k <= 6
    print(ways(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/**
 * 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-05 08:50
 * update_at: 2026-10-05 08:50
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 205; // n 的上界（6 < n <= 200）
const int MAXK = 10;  // k 的上界（2 <= k <= 6）

ll f[MAXN][MAXK]; // f[i][j]：把 i 拆成 j 个正整数、不计顺序的方案数

int main() {
    ll n, k;
    scanf("%lld %lld", &n, &k);

    // 边界：拆成 1 份只有一种（整块给它）；份数比总和还大则无解
    for (ll i = 0; i <= n; i++) {
        f[i][1] = 1;
        for (ll j = 2; j <= k; j++) {
            f[i][j] = 0; // 先默认无解，保证 i < j 时取到 0
            if (i >= j) {
                // 按最小值是否为 1 分类：
                // 最小值 = 1 → 删掉一个 1 → f[i-1][j-1]
                // 最小值 ≥ 2 → 每份减 1   → f[i-j][j]
                f[i][j] = f[i - 1][j - 1] + f[i - j][j];
            }
        }
    }

    printf("%lld\n", f[n][k]);
    return 0;
}

目录

题目描述

思路

参考代码