球盒模型

一句话算法

球盒模型先问四件事：球是否相同、盒是否相同、盒是否允许为空、每盒容量是否受限。

问题模型

把“若干个球放进若干个盒子”看成一个统一模型：

• 球不同：球有编号，例如学生、任务、不同物品。
• 球相同：只关心数量，例如苹果、金币、相同筹码。
• 盒子不同：盒子有编号，例如第 1 组、第 2 组、A 机器、B 机器。
• 盒子相同：交换两个盒子的名字不产生新方案。
• 允许空盒：某些盒子可以没有球。
• 不允许空盒：每个盒子至少一个球。

这类题的难点不在计算公式，而在建模。题面只要改变“是否相同”“是否允许空”，答案模型就会完全变化。

核心直觉

盒子不同，就要考虑顺序；盒子相同，就要消除顺序带来的重复。

球不同，通常在选具体对象；球相同，通常在分配数量。

所以判断模型时，可以用下面这张表：

球	盒子	空盒	常见模型	典型答案
不同	不同	每盒恰好一个	全排列	$n!$
不同	不同	选 $m$ 盒放满	排列	$P(n,m)$
不同	相同	每盒恰好一个	组合	$C(n,m)$
不同	相同	不允许空，可多放	第二类 Stirling 数	$S(n,m)$
不同	不同	不允许空，可多放	满射计数	$m!S(n,m)$
不同	相同	允许空，可多放	分成不超过 $m$ 组	$\sum_{k=1}^{m}S(n,k)$
相同	不同	不允许空，可多放	正整数解	$C(n-1,m-1)$
相同	不同	允许空，可多放	非负整数解	$C(n+m-1,m-1)$
相同	相同	允许空，可多放	整数划分	$p_m(n)$

算法步骤

做球盒题时按这个顺序判断：

1. 看球是否有编号。
2. 看盒子是否有编号。
3. 看每个盒子是否必须非空。
4. 看每个盒子是否只能放一个球。
5. 对照模型表选择公式或 DFS。

常见化简：

• “球不同、盒不同、每盒一个”就是排列。
• “球不同、盒相同、每盒一个”就是组合。
• “球相同、盒不同、可多放”就是方程整数解。
• “球不同、盒相同、可多放且非空”就是第二类 Stirling 数。

算法证明

关键思想： 每个模型都在处理“重复是否算新方案”。

1. 盒子不同：盒子编号是方案的一部分，交换两个盒子的内容会得到新方案。
2. 盒子相同：盒子编号不是方案的一部分，交换盒子内容不应重复计数。
3. 球不同：要记录每个具体球去了哪里。
4. 球相同：只记录每个盒子里有多少个球。

因此模型表中的每一行，本质上都是在明确“方案的唯一表示”。唯一表示确定后，公式或 DFS 的状态就确定了。

复杂度分析

公式计数通常是 $O(1)$ 或 $O(nm)$ 预处理组合数。

如果需要输出所有方案，时间复杂度至少等于方案数量：

• 排列输出：$O(n \cdot n!)$。
• 组合输出：$O(m \cdot C(n,m))$。
• Stirling 方案输出：$O(n \cdot S(n,m))$。

代码实现

球盒模型是总览页，具体模板分散在对应专题：

• 全排列
• 组合
• 重复元素全排列
• 第二类 Stirling 数

测试用例

问题：5 个相同球放入 2 个不同盒子，允许空盒。

等价于：

$$x_1+x_2=5,\quad x_1,x_2\ge 0$$

答案：

$$C(5+2-1,2-1)=C(6,1)=6$$

对应方案：

0 5
1 4
2 3
3 2
4 1
5 0

应用分类详解

球盒模型的本质是把对象分配到容器中，并判断哪些分配方案算相同。

一、选人、排队、分配任务

典型模式： 学生、任务、物品都有编号。

识别信号： 题面出现“第 i 个人”“第 j 个任务”“分到不同组/机器/盒子”。

核心建模： 球不同；盒子是否不同取决于组或机器有没有名字。

应用场景	经典题目	核心思路
排队	luogu-P1706	不同球放入不同位置
选若干人	luogu-P1157	不同球放入相同盒，每盒一个
分组	luogu-P1287	不同球分到相同非空盒

二、整数分配和隔板法

典型模式： 物品完全相同，只关心每个盒子拿到多少。

识别信号： 苹果、金币、糖果、方案只看数量。

核心建模： 球相同；盒子不同就是整数解，盒子相同就是整数划分。

应用场景	经典题目	核心思路
相同物品分给不同人	隔板法基础题	正整数解或非负整数解
放苹果	noiopenjudge-ch0202/666/	相同球放入相同盒，按数量定序

三、集合划分

典型模式： 把不同元素划分成若干个非空集合，集合之间没有名字。

识别信号： “分成若干组”“组之间不区分顺序”“每组非空”。

核心建模： 第二类 Stirling 数 $S(n,m)$。

应用场景	经典题目	核心思路
不同球分相同盒	luogu-P1287	$S(n,m)$
不同球分不同盒且非空	满射计数	$m!S(n,m)$

经典例题

• luogu-P1157 组合的输出：不同球，相同盒，每盒一个。
• luogu-P1287 盒子与球：不同球，相同非空盒，第二类 Stirling 数。
• noiopenjudge-ch0202/666/ 放苹果：相同球，相同盒，整数划分模型。
• luogu-P1706 全排列问题：不同球，不同位置，每盒一个。

参考

• 本书相关章节：第二类 Stirling 数