骨牌1

题目描述

给定正整数 $n$ 和 $k$ ，求把 $n$ 拆成恰好 $k$ 个正整数之和的方案数，顺序不同视为同一种。数据范围满足 $n \le 200$ ， $k \le 7$ 左右。

思路

由于加法可交换，每个方案都可以唯一对应一个非降序列 $1 \le a_1 \le a_2 \le \dots \le a_k$ 且和为 $n$ 。用 ways(rest, parts, low) 表示还要把 rest 分成 parts 段、且下一段最小为 low 的方案数。枚举当前段 head，下界是非降约束 low，上界收紧为 rest / parts（余下每段都至少为 head）。parts == 1 时只要 rest >= low 就唯一方案，parts == 0 时只有 rest == 0 才计 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#!/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-10-01 02:10
# update_at: 2026-10-01 02:10

import sys
from functools import cache


@cache
def ways(rest: int, parts: int, low: int) -> int:
    """把 rest 拆成 parts 个非降正整数、且每段都不小于 low 的方案数。

    非降约定让同一个多重集合只有一种写法，于是"数拆分方案"等同于"数非降序列"。
    """
    if parts == 0:
        return 1 if rest == 0 else 0          # 恰好填满才算一个方案
    if parts == 1:
        return 1 if rest >= low else 0        # 只剩一段时，长度一旦合法就唯一
    # 首段 head 的下界是非降约束 low；上界来自「余下 parts-1 段每段至少 head」
    # 即 head + (parts-1)*head <= rest，等价于 head <= rest // parts。
    heads = range(low, rest // parts + 1)
    return sum(ways(rest - head, parts - 1, head) for head in heads)


def solve() -> None:
    n, k = map(int, sys.stdin.buffer.read().split())
    print(ways(n, k, 1))


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/**
 * 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-06 01:49
 * update_at: 2026-10-06 01:49
 */
#include <iostream>
#include <cstring>
using namespace std;

typedef long long ll;

ll n, k;

// memo[rest][parts][low] 表示把 rest 拆成 parts 个非降正整数、且每段不小于 low 的方案数。
// n 最大约 200，k 最大约 7，low 最大约 n，用 -1 表示未计算。
ll memo[205][10][205];

// 返回方案数。
ll ways(ll rest, ll parts, ll low) {
    if (parts == 0) return rest == 0 ? 1 : 0;        // 恰好填满才合法
    if (parts == 1) return rest >= low ? 1 : 0;      // 只剩一段，和已固定
    ll &ans = memo[rest][parts][low];
    if (ans != -1) return ans;
    ans = 0;
    // head 的下界是非降约束 low；上界来自余下每段至少 head，即 head * parts <= rest。
    ll up = rest / parts;
    for (ll head = low; head <= up; ++head) {
        ans += ways(rest - head, parts - 1, head);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(memo, -1, sizeof(memo));
    cin >> n >> k;
    cout << ways(n, k, 1) << '\n';
    return 0;
}

目录

题目描述

思路

参考代码