题解：将x分解为k个不同组合数的和

算法标签

• 组合数
• 构造法
• 贪心思想

问题分析

题目要求将整数 $x$ 分解为恰好 $k$ 个不同的组合数之和，且每个组合数 $C(n,m)$ 需满足 $0 \leq m \leq n \leq x$。组合数的“不同”定义为 $(n_1, m_1) \neq (n_2, m_2)$（即 $n$ 不同或 $m$ 不同）。

核心思路

组合数的选择

观察组合数的性质：

• $C(n, 0) = 1$（从 $n$ 个元素中选 $0$ 个，仅有 $1$ 种方法）。
• $C(a, 1) = a$（从 $a$ 个元素中选 $1$ 个，有 $a$ 种方法）。

构造方案

利用上述性质，构造 $k$ 个不同的组合数：

1. 前 $k-1$ 个组合数：选择 $(n, m) = (i, 0)$（$i$ 从 $1$ 到 $k-1$）。
   这些组合数均为 $C(i, 0) = 1$，且因 $n$ 不同，组合数彼此不同。
2. 第 $k$ 个组合数：选择 $(n, m) = (x - (k-1), 1)$。
   该组合数的值为 $C(x - (k-1), 1) = x - (k-1)$，确保总和为：$$(k-1) \times 1 + (x - (k-1)) = x$$

正确性验证

1. 总和正确性：
   前 $k-1$ 个组合数的和为 $k-1$，第 $k$ 个组合数为 $x - (k-1)$，总和为 $x$，满足要求。

2. 组合数不同：

   • 前 $k-1$ 个组合数的 $(n, m)$ 为 $(1,0), (2,0), \dots, (k-1, 0)$，因 $n$ 不同，彼此不同。
   • 第 $k$ 个组合数的 $m=1$，而前 $k-1$ 个的 $m=0$，因 $m$ 不同，与前 $k-1$ 个均不同。

3. 范围合法性：

   • 前 $k-1$ 个的 $n = i$（$1 \leq i \leq k-1$），因 $k \leq 10^3$ 且 $x \geq 1$，故 $i \leq x$。
   • 第 $k$ 个的 $n = x - (k-1)$，由题目“数据保证有解”可知 $x \geq k-1$，故 $n \geq 1$，且 $m=1 \leq n$，满足 $0 \leq m \leq n \leq x$。

代码解析

#include <stdio.h>

int main() {
    long long x, k;
    scanf("%lld %lld", &x, &k);

    // 输出前k-1个组合数：(1,0), (2,0), ..., (k-1, 0)
    for (long long i = 1; i < k; i++) {
        printf("%lld %d\n", i, 0);
    }

    // 输出第k个组合数：(x - k + 1, 1)
    printf("%lld %d\n", x - k + 1, 1);

    return 0;
}

• 前k-1个组合数：通过循环生成 $(i, 0)$，确保每个组合数为 $1$ 且彼此不同。
• 第k个组合数：计算 $n = x - k + 1$，$m=1$，其值为 $x - (k-1)$，保证总和为 $x$。

复杂度分析

• 时间复杂度：$O(k)$，仅需循环 $k-1$ 次，输出 $k$ 行结果。
• 空间复杂度：$O(1)$，仅使用常数个变量。

该方法高效且通用，可满足 $x \leq 10^9$、$k \leq 10^3$ 的数据范围要求。