本文详解如何将“分糖果”问题建模为带约束的整数划分问题，通过数学转化（零允许→正整数划分）、递推关系推导及空间优化dp实现，将时间复杂度稳定控制在 o(c×d)，轻松应对 1000 组大规模输入。
本文详解如何将“分糖果”问题建模为带约束的整数划分问题，通过数学转化（零允许→正整数划分）、递推关系推导及空间优化dp实现，将时间复杂度稳定控制在 o(c×d)，轻松应对 1000 组大规模输入。
该问题本质是：给定 D 个孩子和 C 颗糖果，要求分配方案满足 非递减顺序（即第 i 名的孩子所得糖果数 ≤ 第 i+1 名），等价于统计所有长度为 D、元素和为 C、且满足 $x_1 \le x_2 \le \cdots \le x_D$ 的非负整数序列个数。
关键洞察在于：这类序列与 整数 C 划分为至多 D 个部分（允许 0）的非递减划分 一一对应。但标准整数划分通常定义为正整数之和，因此我们采用经典平移技巧——令
$$
y_i = x_i + 1 \quad (i = 1,2,\dots,D)
$$
则 $y_i \ge 1$ 且严格满足 $y_1 \le y_2 \le \cdots \le y_D$，其和为 $C + D$。此时，$(y_1,\dots,y_D)$ 正是整数 $C+D$ 的一个 恰好 D 部分的（正整数）非递减划分，即「D-分拆数」$p(C+D,\, D)$。
该分拆数满足如下经典递推式（可由 Ferrers 图共轭或生成函数导出）：
$$ \begin{aligned} p(n, k) &= \begin{cases} 1 & n = k = 0 \ 0 & n \le 0 \text{ 或 } k \le 0 \ p(n - k,\, k) + p(n - 1,\, k - 1) & \text{其他} \end{cases} \end{aligned} $$
其中：
- $p(n - k, k)$：表示所有部分 ≥ 2 的 D-分拆（每部分减 1 后仍为 D-分拆）；
- $p(n - 1, k - 1)$：表示至少有一个部分为 1 的 D-分拆（删去该 1 后变为 (D−1)-分拆）。
因此，原问题答案即为 p(C + D, D)。
✅ 推荐实现：空间优化的二维 DP（Bottom-up）
为避免递归开销与栈溢出，并支持 Q ≤ 1000 批量查询，我们预处理一个全局 DP 表 dp[d][c]，其中 dp[d][c] = p(c, d)，范围覆盖最大 D=100、最大 C=5000+100=5100：
MOD = (1 = d else 0
term2 = dp[d - 1][c - 1] if c >= 1 and d >= 1 else 0
dp[d][c] = (term1 + term2) % MOD
# 处理输入
import sys
input = sys.stdin.read().split()
q = int(input[0])
idx = 1
out_lines = []
for _ in range(q):
d = int(input[idx])
c = int(input[idx + 1])
idx += 2
# answer = p(c + d, d)
res = dp[d][c + d] if (c + d) <h3>⚠️ 注意事项与优化要点</h3>
- 边界安全：c + d 最大为 5000 + 100 = 5100，在 MAX_C = 5100 下完全覆盖，无需运行时判断越界。
- 空间压缩（进阶）：若内存受限，可仅保留两行 dp_prev[c] 和 dp_curr[c]，将空间从 O(D×C) 降至 O(C)，但需注意 dp_curr[c] 依赖 dp_curr[c-d]（同层前向），故推荐使用完整二维表以保逻辑清晰。
- 勿混淆模型：原始错误代码中尝试暴力枚举所有组合并事后排序校验，时间复杂度高达 $O(C^D)$，完全不可行；而早期 DP 版本中的状态定义有误（如 dp[i][j] += dp[i][j-i] 缺失语义支撑），导致结果偏差。
- 模运算位置：务必在每次加法后取模，防止整数溢出（Python 虽支持大整数，但题目明确要求模 2^30−1）。
✅ 总结
本题是算法优化的经典范例：
? 建模转换 是提速前提——将“非递减非负分配”转化为“正整数 D-分拆”；
? 数学递推 提供最优子结构——p(n,k) = p(n−k,k) + p(n−1,k−1) 是核心加速引擎；
? 预处理 + 查表 是应对多查询的黄金策略——用 O(D×C) 空间换 O(1) 单次查询，总耗时稳定在毫秒级。
最终代码可在 1000 组输入下稳定通过时限，兼具正确性、效率与可维护性。
