题解

思路

八个答案分别对应四类经典计数对象。

• 相同球、相同盒：整数拆分；
• 相同球、不同盒：隔板法；
• 不同球、相同盒：第二类 Stirling 数；
• 不同球、不同盒：函数或满射计数。

记 $P(n,k)$ 为把 $n$ 拆成恰好 $k$ 个正整数且不计顺序的方案数，$S(n,k)$ 为第二类 Stirling 数。

$m\le2$

当盒子不超过两个时，整数拆分和 Stirling 数都有闭式。例如 $m=2$ 时，至多两部分的拆分数为 $\lfloor n/2\rfloor+1$，恰好两部分为 $\lfloor n/2\rfloor$，且

$$S(n,2)=2^{n-1}-1.$$

其余答案也由隔板法和 $2^n$ 直接得到。

$m\ge n$

非空盒数不可能超过球数，因此“允许空盒”的相同盒、不同球相同盒两种情形分别饱和为整数拆分数 $p(n)$ 与 Bell 数 $B_n$。所有“不允许空盒”的答案在 $m>n$ 时为 $0$，在 $m=n$ 时只有每盒一个球的相应方案。这个结构可独立计算全部八项。

做法

整数拆分

利用 Ferrers 图共轭，$n$ 拆成至多 $m$ 部分的方案数，等于使用部件大小 $1,2,\ldots,m$ 的完全背包方案数。令一维数组 $p[0]=1$，依次加入这些部件即可。

恰好 $m$ 个正部分时，每部分先减去 $1$，答案变为把 $n-m$ 拆成至多 $m$ 部分，即 $p[n-m]$。

组合数

相同球放入不同盒时，隔板法给出：

$$\text{无空盒}=\binom{n-1}{m-1},\qquad \text{允许空盒}=\binom{n+m-1}{m-1}.$$

边界 $n=m=0$ 单独按空分配的一种方案处理。

Stirling 数

第二类 Stirling 数满足

$$S(i,k)=S(i-1,k-1)+kS(i-1,k),\qquad S(0,0)=1.$$

因此不同球、相同盒且无空盒的答案为 $S(n,m)$；允许空盒时，非空盒数可以是 $0$ 到 $m$，答案为 $\sum_{k=0}^{m}S(n,k)$。

可区分盒

每个不同的球独立选择一个盒子，允许空盒的答案为 $m^n$。要求无空盒时，先把球划分成 $m$ 个非空无标号集合，再把这些集合排列给盒子，答案为

$$m!S(n,m).$$

正确性证明

引理 1

一维完全背包得到的 $p[t]$ 等于 $t$ 的至多 $m$ 部分拆分数。

证明。 背包中每个部件大小可使用任意次，对应一个非增整数拆分的各部件；Ferrers 图共轭把“最大部件不超过 $m$”与“部分数不超过 $m$”双射。∎

引理 2

$S(n,m)$ 与 $m!S(n,m)$ 分别计数不同球放入相同非空盒、不同非空盒的方案。

证明。 $S(n,m)$ 把球集划分为 $m$ 个非空无标号块，每块对应一个相同盒；盒子有标号时再把 $m$ 个块双射到盒子，共乘 $m!$。∎

定理

算法输出的八个数分别等于题目八种分配方案数。

证明。 前两项由引理 1 及“每部分先减一”得到；第三、四项由隔板法得到；第五、六项由引理 2 以及枚举非空盒数得到；第七项是每球独立选择盒子；第八项由引理 2 的有标号版本得到。八项与题目顺序一致。∎

复杂度

时间复杂度 $O(nm)$，空间复杂度 $O(n+m)$。