解题思路

本题等价于把正整数 $n$ 划分为恰好 $k$ 个正整数的有序序列。直接的划分型动态规划如下：

设 dp[s][t] 表示用恰好 t 枚硬币，面额之和为 s 的有序方案数。 转移时，最后一枚硬币取值为 x (1 ≤ x ≤ s)，那么前面 t-1 枚的和是 s-x，于是：

边界：dp[0][0] = 1（选 0 枚凑出和 0 的方案为 1），其他如 dp[s][0]=0 (s>0)。

因为题目给的面额有 $1,2,\ldots,10^9$ 且不限张数，但由于每枚硬币至少为 1，且总和为 s，最后一枚硬币最大只可能取到 s，所以上述状态和转移成立。

复杂度分析

• 时间复杂度：外层枚举 s=1..n，内层枚举 t=1..k，再枚举最后一枚的面额 x=1..s，总体 $O(n^2 k)$。
• 空间复杂度：使用二维表 dp，规模约为 $(n+1)\times(k+1)$，即 $O(nk)$。

代码实现

Python

# 题面功能放在外部函数里
def count_sequences(n, k):
    # dp[s][t]：恰好用 t 枚硬币凑成和 s 的方案数
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1  # 边界：0 枚硬币凑出 0 的方案为 1

    # 逐步累加构造
    for s in range(1, n + 1):
        # t 不可能超过 s（至少每个硬币为 1）
        for t in range(1, min(k, s) + 1):
            total = 0
            # 枚举最后一枚硬币面额 x
            for x in range(1, s + 1):
                total += dp[s - x][t - 1]
            dp[s][t] = total
    return dp[n][k]

if __name__ == "__main__":
    # ACM 风格输入输出：一行两个整数
    import sys
    data = sys.stdin.read().strip().split()
    n, k = map(int, data[:2])
    ans = count_sequences(n, k)
    print(ans)

Java

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    // 外部函数：计算恰好用 k 枚硬币凑成 n 的方案数（有序）
    static long countSequences(int n, int k) {
        // 使用 long，数据范围下 C(62,31) 约 4.7e18，可放入 long
        long[][] dp = new long[n + 1][k + 1];
        dp[0][0] = 1L; // 边界

        for (int s = 1; s <= n; s++) {
            int tMax = Math.min(k, s);
            for (int t = 1; t <= tMax; t++) {
                long total = 0L;
                // 枚举最后一枚硬币的面额 x
                for (int x = 1; x <= s; x++) {
                    total += dp[s - x][t - 1];
                }
                dp[s][t] = total;
            }
        }
        return dp[n][k];
    }

    public static void main(String[] args) {
        // ACM 风格输入输出
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        int k = sc.nextInt();
        sc.close();
        long ans = countSequences(n, k);
        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 外部函数：计算恰好用 k 枚硬币凑成 n 的有序方案数
// 使用 unsigned long long 足以覆盖本题数据范围
unsigned long long count_sequences(int n, int k) {
    vector<vector<unsigned long long>> dp(n + 1, vector<unsigned long long>(k + 1, 0ULL));
    dp[0][0] = 1ULL; // 边界

    for (int s = 1; s <= n; ++s) {
        int tMax = min(k, s);
        for (int t = 1; t <= tMax; ++t) {
            unsigned long long total = 0ULL;
            // 枚举最后一枚硬币面额 x
            for (int x = 1; x <= s; ++x) {
                total += dp[s - x][t - 1];
            }
            dp[s][t] = total;
        }
    }
    return dp[n][k];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    auto ans = count_sequences(n, k);
    cout << ans << "\n";
    return 0;
}

题面描述

给定两个正整数 $n,k$。你有面额为 $1,2,3,\ldots,10^9$ 的硬币，每种面额数量无限。你必须恰好选出 $k$ 枚硬币，并且要求它们的总面额之和为 $n$。 选择的顺序不同视为不同方案（如 $2,1$ 与 $1,2$ 记为两种）。求满足条件的方案数；

输入输出

输入： 一行两个整数 $n,k$。

输出： 输出一个整数，表示恰好用 $k$ 枚硬币凑成面额 $n$ 的方案数。

数据范围

• $1 \le n \le 63$
• $1 \le k \le n$

样例

输入

3 2

输出

2

说明 可行序列：1,2，2,1。

输入

4 3

输出

3

说明 可行序列：1,1,2，1,2,1，2,1,1。