一、题型描述

已知：

并且每个变量都有上限限制：

求非负整数解的个数。

二、常用方法

1. 无限制分配公式（基础）

当没有上限限制时：

这是 Stars and Bars（插板法）的基础公式，所有有限制的题都可以从它扩展。

2. 容斥法（通用型，任何限制都能用）

步骤

1. 先算 无限制解数：

2. 逐步剔除 不符合上限的解。

   • 如果第 $i$ 人超过上限 $m_i$：令 $x_i' = x_i - (m_i+1)$，再解新的方程。

3. 用容斥公式：

其中 $T_k$ 表示恰好 $k$ 个人超限后的解数。

特点

• 优点：适合上限差异大、总数 S 不接近上限总和的题。
• 缺点：步骤多，计算量可能大。

3. 补足法（缺额法）（高效型，适合总数接近上限总和）

条件

当：

即 总数接近上限总和，优先考虑补足法。

原理

设：

则：

此时每个 $y_i \ge 0$，就是一个无上限分配问题。

公式

其中 $M = m_1 + m_2 + \dots + m_n$。

例

本题：

• $n=3$，$m_i=8$，$S=20$，$M=24$
• 缺额总和：$M-S = 4$
• 解数：

一步得出。

优点

• 计算一步到位。
• 特别适合 “总数接近上限总和” 的题。
• 考试中可秒算。

三、对比选择

四、考试建议

1. 先看总数与上限总和差距：差距小 → 补足法；差距大 → 容斥法。
2. 人数少时（$n \le 4$）容斥法计算也不复杂，可直接用。
3. 注意非负整数解公式要熟练背：$\binom{S+n-1}{n-1}$ 和 $\binom{d+n-1}{n-1}$（补足法）。