球盒问题详解
概述
球盒问题目的是求解将小球放入盒子中的不同方案数，属于组合数学问题。
根据小球是否相同，盒子是否相同可以分为四类问题
根据盒子是否可空可以扩展为八个子问题。
这八个问题模型非常简单，应用广泛，但是具体计算有一定难度。
充分理解这些问题对组合数学和算法的学习很有帮助。
以下假设小球个数为\(n\)，盒子个数为\(m\)，如果盒子不可为空时 有\(n>=m\)
首先明确几个潜规则：
盒子不存在排列问题。盒子如何放置如何组合，都不影响方案的区分。
如一个小球放入两个相同盒子中，这两个盒子是上下放置的，不论小球放上面还是下面，都只算一种方案。
一个盒子里的多个小球不存在排列问题
如两个不同小球放入一个盒子里，是一种方案。忽略这两个小球在盒子内部的任意布局。
如果要求盒子不能为空，但是小球数量小于盒子数，约定方案数为零
为了保证充分理解所谓的【相同】与【不同】，这里先举一个实际的例子。
以3个球放进2个盒子为例，均要求盒子不可为空。
球同盒相同
你有3个同样的苹果，需要分成两份。由于要求盒子不可为空，所以每份至少有一个苹果。
显然只有一种1+2分法。请务必注意没有所谓的2+1分法，只是分成两份，这两份并没有任何的排列问题。
记方案数为\(f_1=1\)
球同盒不同
你有3个同样的苹果，需要分给AB两个人。
显然可以A1 B2或者A2 B1，这是两种方案。
记方案数为\(f_2=2\)
理解有难点，请充分理解盒不同的概念。
进阶提问：盒子个数设为\(m\)，问\(f_2=f_1*A_m^m\)是否成立？
这个问题的意义是，由于\(f_1\)是分\(m\)份的方案数，然后对这\(m\)份进行全排列，对应给\(m\)个人，看起来就应该是\(f_2\)？
然而是错误的，如小球个数为\(n=4\)，盒子数为\(m=3\)，当一种划分为[1,1,2]时，显然对这种划分进行全排列会产生冗余重复方案。
球不同盒相同
你有3个水果，1苹果1香蕉1橘子，需要分成两份。
显然有三种方案，即每个水果单独一份时的方案数。
记方案数为\(f_3=3\)
球不同盒不同
你有3个水果，1苹果1香蕉1橘子，需要分给AB两个人。
A可以三种水果各取一个，B取另外两个，这有三种方案。
相应的B也可以各取一个，A取另外两个，也是三种方案。
故总计有\(f_4=6\)
进阶提问：问\(f_4=f_3*A_m^m\)是否成立？
成立，由于水果都是不同的，所以必然不会有重复排列。
再次提醒，需要充分理解【相同】与【不同】的概念，本例子中意义是相对清晰的，实际应用中描述可能相当有迷惑性，稍不留神就无法建立正确的模型。
下面详细介绍如何计算不同问题的方案数。
前置
组合数公式
首先计算组合数\(C_n^m\)和\(A_n^m\)
对于排列数\(A_n^m\) 表示从n个不同元素中选出m个元素形成的不同排列数。
顾名思义，第1个元素有\(n\)种选法，第2个元素剩下\(n-1\)种选法，以此类推，最后一个元素有\(n-m+1\)种选法。
故\(A_n^m=n*(n-1)*(n-2)*...*(n-m+1)=\frac{n!}{(n-m)!}\)
而\(C_n^m\)表示选出\(m\)个元素但是不排列，所以去掉排列的重复部分
故\(C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}\)
其中计算\(C_n^m\) 一种常用方法是递推
\(C_i^j=C_{i-1}^{j-1}+C_{i-1}^{j}\)
具体原理是考虑第\(i\)个元素是否选取
如果选择\(i\)，则剩下的\(i-1\)个元素中需要选择\(j-1\)个元素，即\(C_{i-1}^{j-1}\)
如果不选择\(i\)，则剩下的\(i-1\)个元素中需要选择\(j\)个元素，即\(C_{i-1}^{j}\)
这种做法通常在复杂度要求不高，或者需要使用递推式的某些情况下使用
更通用的做法是基于组合数公式直接计算。
余数处理
由于组合数结果非常大，故一般情况下会对常见大质数求余 如\(1e^9+7\)或\(998244353\)等
由于存在除数，简单的余数计算无法满足，处理方式一般有两种，一种是分解质因数做约分(不常用 且复杂度高），另一种就是【逆元】
根据费马小定理简单可得 \(\frac{a}{b}\%p=a*pow(b,p-2,p)\%p\)
也就是\(\frac{1}{b}\)对\(p\)的余数=\(pow(b, p-2,p)\)
\(pow(b, p-2,p)\)表示\(b\)的\(p-2\)次方对\(p\)的余数
其中\(p\)为常见大质数 所以直接计算\(pow\)复杂度较高，一般使用快速幂
快速幂的通用模板
using i64 = long long;
i64 power(i64 x, i64 y, i64 p){
i64 r = 1;
while(y > 0){
if((y & 1) == 1) r = r * x % p;
y >>= 1;
x = x * x % p;
}
return r;
}
预处理所有\( 则\(C_i^j=\frac{i!}{j!(i-j)!}=f[i]*pow(f[j],p-2,p)\%p*pow(f[i-j],p-2,p)\%p\) 单次计算复杂度为\(O(log(p))\) 扩展问题： 小球是否允许不放完。 一般不允许，如果出现，通常做法就是先枚举放了几个，这样实际转换为通用问题的方案和。 小球有的相同 有的不相同。或者说是若干组相同小球。 一般来说不同小球之间是相互独立的，多数可以乘法原理计算，即各自小球的方案数的乘积 下面具体计算不同的球盒问题 球相同盒不同 关键词：隔板法。 球相同盒不同，盒子不可以为空 注意此时一般 \(n>=m\)，否则会导致有盒子为空 球是完全相同的，所以哪个盒子先放没有区别，也就是第一个盒子从所有球取 \(c_1\) 个，第二个盒子再取 \(c_2\) 个，... 最后盒子 \(c_m\) 个， (\(c_i>=1,(\sum_{i=1}^{m}c_i)=n\)) ，这样操作对应了所有的方案数。 隔板法：球之间的缝隙总共有 \(n−1\) 个(不包括边界)，从其中任选 \(m−1\) 个缝隙插入隔板，会将所有球分隔为 \(m\) 段 所以答案为 \(f(n,m)=C_{n−1}^{m−1}\) 。 等价问题为：方程式\(x_1+x_2+...x_m=n\)的正整数解 球相同盒不同，盒子可以为空 发散一下思维，把球增加到 \(n+m\) 个，此时把这 \(n+m\) 个球放进 \(m\) 个盒子里，然后求不允许为空的方案数，这就转换为上面的问题，即 \(f'(n+m,m)=C_{n+m−1}^{m−1}\) 。 重点来了：当分配完毕后，由于每个盒子不为空，所以一定可以各扣除一个球，总共会扣除\(m\)个，这就对应了\(n\)个球允许为空的方案数。 综上方案数\(f'(n,m)=f(n+m,m)=C_{n+m−1}^{m−1}\) 等价问题为：方程式\(x_1+x_2+...x_m=n\)的非负整数解 同样对每个\(x\)假设\(y=x+1\)，问题转换为\(y_1+y_2+...y_m=n+m\)的正整数解，可以得到同样结论。 例题 1641. 统计字典序元音字符串的数目 给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。 字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。 典型球同盒不同，盒可以为空模型。 n 个球，5个盒。 所以答案就是 \(f'(n,5)=f(n+5,5)=C_{n+4}^4\) 以下是LeetCode核心模式代码 //解法1 直接计算 class Solution { public: int countVowelStrings(int n) { int ans = 1; for(int i = 0; i < 4; i++) ans = ans * (n - i + 4); for(int i = 0; i < 4; i++) ans = ans / (i + 1); return ans; } }; //解法2 套用模板 class Solution { public: //////////////组合数模板开始 using i64 = long long; i64 p = 1e9 + 7; vector void initFac(int n){ f.resize(n + 1); f[0] = 1; for(int i = 1; i <= n; i++) f[i] = f[i - 1] * i % p; } i64 power(i64 x, i64 y, i64 p = 1e9 + 7){ i64 r = 1; while(y > 0){ if((y & 1) == 1) r = r * x % p; y >>= 1; x = x * x % p; } return r; } i64 Anm(int n, int m){ return f[n] * power(f[n - m], p - 2, p) % p; } i64 Cnm(int n, int m){ return Anm(n, m) * power(f[m], p - 2, p) % p; } //////////////组合数模板结束 int countVowelStrings(int n) { initFac(n + 4); //初始化阶乘范围 return (int)Cnm(n + 4, 4); //套用模板 } }; 例题 2338. 统计理想数组的数目 有难度，其中用到了多组相同球放入不同盒子的模型。各组相互独立，各自方案数乘积即可。 假设有\(k\)组球，个数分别为\(c_1\) \(c_2\) ... \(c_k\) 则总的方案数为\(f=\prod_{i=1}^{k}C_{n+c_i-1}^{n-1}\) //核心逻辑 int idealArrays(int n, int maxValue) { initFac(n + 30); //组合数模板 i64 ans = 0; for (int i = 1; i <= maxValue; i++){ auto factors = divide(i); //分解质因数 i64 r = 1; for(auto [k, c] : factors){ r = r * Cnm(n + c - 1, n - 1) % mod; //球同盒不同 盒子可以为空 多组乘法原理 } ans = (ans + r) % mod; } return (int)ans; } 球不同盒相同 关键词：第二类斯特林数 必须再次加深下球不同盒相同的理解 对比一下球相同盒不同的区别： 球相同盒不同 你有三个相同的苹果，分给两个不同的人A和B，分法是A1B2或者A2B1，总计两种方案。 球不同盒相同 你有三个不同的水果，如苹果香蕉橘子各1个，分成两份。分法是每个水果单独一份，总计三种方案。 注意苹果+香蕉橘子和香蕉橘子+苹果是完全没有区别的。 下面具体分析： 球不同盒相同，盒子不可以为空 我们模拟下把3个不同水果分成2份的情况，来推导计算方案。 用\(f(n,m)\)表示把\(n\)个不同水果分成\(m\)份的方案数 显然\(f(1,1)=1\) 即只有1个水果 只能形成1种方案。 \(f(2,1)=1\)也是显然的，因为两个不同水果分成一份，只能合并放一起。 继续\(f(2,2)=1\)，因为2个不同水果分成2份只能是分开放一种方案。 如何计算\(f(3,2)\)？ 由于之前计算好了两个不同水果的情况，对于新增的第三个水果： 如果它单独形成1份，则之前的两个水果必须合并为1份，即\(f(2,1)\) 如果它不是单独形成1分，则要在之前的两份里任选一份(\(C_2^1=2\))补进去，即\(2*f(2,2)\) 综合两种情况有\(f(3,2)=f(2,1)+2*f(2,2)\) 更一般的，计算\(f(n,m)\)，当枚举到第\(i\)个水果时 \(f(i,j)=f(i-1,j-1)+j*f(i-1,j)\) 初始条件\(f(0,0)=1\) 递推至\(f(n,m)\)即可 这就是著名的第二类斯特林数(Stirling Number) 第二类斯特林数 表示将 n 个两两不同的元素，划分为 m 个互不区分的非空子集的方案数。 记为 S(n,m) 一些性质： \(S(0,0)=S(n,1)=S(n,n)=1\) 其中 \(S(0,0)=1\) 视为初值 \(S(n,2)=2^{n−1}−1\) 每个球有两种选择方式，不允许所有球都跟第一个球放一个盒子里。则总共有\(2^n-2\)种方式，注意这种放法包含了对称重复，故应除2。 \(S(n,n−1)=C_n^2\) 只有两个球是放一个盒子里的，选择两个球的方案数为\(C_n^2\) 例题 1692. 计算分配糖果的不同方式 现有 n 颗 不同 糖果（分别标记为 1 到 n ）和 k 个相同的手袋。请把糖果分配到各个手袋中并保证每个手袋里至少有一颗糖果。 已知整数 n 和 k, 请返回分配糖果的不同方式。返回的答案如果数值太大，请取1e9 + 7的模，并返回。 1 <= k <= n <= 1000 球不同盒相同，盒子不可以为空模板题。第二类斯特林数模板题 class Solution { public: int mod = (int)1e9 + 7; int waysToDistribute(int n, int k) { vector f[0][0] = 1; for(int i = 1; i <= n; i++){ //二维循环的话 本行和下面一行交换没有影响 for(int j = 1; j <= k; j++){ f[i][j] = (f[i - 1][j - 1] + 1L * j * f[i - 1][j] % mod) % mod; } } return f[n][k]; } }; 经典dp空间优化，考虑到f[i]只与f[i-1]有关，显然可以减少一维 class Solution { public: int mod = (int)1e9 + 7; int waysToDistribute(int n, int k) { vector f[0] = 1; for(int i = 1; i <= n; i++){ for(int j = min(i, k); j > 0; j--){ //注意j起点至多为i 因为球不能少于盒子 f[j] = (f[j - 1] + 1L * j * f[j] % mod) % mod; } f[0] = 0; //只有0个球放进0个盒子方案数是1 } return f[k]; } }; 球不同盒相同，盒子可以为空 如果理解足够充分，可以意识到这个问题实际是有点迷惑人的简单问题。 如果盒子可以为空，如空1个盒子，则方案数简单从\(f'(n,m)\)变成\(f'(n,m-1)\) 而盒子至多可以空\(m-1\)个，枚举空了多少个盒子 答案为所有情况之和 或者说枚举放1-m个盒子的方案数之和 即\(f'(n,m)=\sum_{k=1}^{m}S(n,k)\) 其中 \(S(n,k)\) 是第二类斯特林数 再次提醒，当盒子完全相同时，所有空的盒子都是一样且无效的。 球不同盒不同 关键词：乘法原理 容斥原理 第二类斯特林数 球不同盒不同，盒子可以为空 由于球盒均不相同，所以每个球放进任意一个盒子都会形成不同的方案。 故每个球有\(m\)种方法，总共有\(n\)个球，由乘法原理简单可知 \(f(n,m)=m^n\) 球不同盒不同，盒子不可以为空 这个问题在本文开头已经提及 问\(f_4=f_3*A_m^m\)是否成立？ 成立，由于水果都是不同的，所以必然不会有重复排列。 所以实际上\(f'(n,m)=S(n,m)*m!\) 容斥原理计算第二类斯特林数 第二类斯特林数可以使用容斥原理计算，这种方式巧妙地把斯特林数与组合数联系起来。 首先如果如果盒子允许为空，已知方案数为\(m^n\) 如何求解盒子不可以为空的方案数？ 假设至少有\(i\)个盒子为空的方案数为\(f[i]\)，则\(f[0]=m^n\)。 由容斥原理可知总的方案数为 \(f'(n,m)=\sum_{i=0}^{m}(-1)^if[i]\) 而对于\(f[i]\)，由于至少有\(i\)个空盒子，选出这\(i\)个空盒子的方法数为\(C_m^i\) 剩下\(m-i\)个盒子，这\(n\)个球可以任意放置，则有\((m-i)^n\)种可能 因此\(f[i]=C_m^i(m-i)^n\) 所以最终方案数为\(f'(n,m)=\sum_{i=0}^{m}(-1)^iC_m^i(m-i)^n\) 由于球同盒不同的方案数实际为\(f'(n,m)=S(n,m)*m!\) 因此可知第二类斯特林数的容斥计算方式为 \(S(n,m)=\frac{1}{m!}\sum_{i=0}^{m}(-1)^iC_m^i(m-i)^n\) 特别注意使用容斥的时间复杂度为\(O(n + mlogU)\) 优于递推的\(O(nm)\) 对于例题 1692. 计算分配糖果的不同方式 使用容斥原理的代码如下 int waysToDistribute(int n, int k) { initFac(n); int invM = power(f[k], p - 2, p); //预处理可以减少一个log系数 i64 ans = 0, g = 1; for(int i = 0; i <= k; i++){ int t = invM * g * Cnm(k, i) % p * power((k - i), n, p) % p; ans = (ans + t + p) % p; //容斥计算可能产生负数 g *= -1; //-1的处理 } return ans; } 例题 3317. 安排活动的方案数 给你三个整数 n ，x 和 y 。 一个活动总共有 n 位表演者。每一位表演者会 被安排 到 x 个节目之一，有可能有节目 没有 任何表演者。 所有节目都安排完毕后，评委会给每一个 有表演者的 节目打分，分数是一个 [1, y] 之间的整数。 请你返回 总 的活动方案数。 答案可能很大，请你将它对 1e9 + 7 取余 后返回。 注意 ，如果两个活动满足以下条件 之一 ，那么它们被视为 不同 的活动： 存在 一个表演者在不同的节目中表演。 存在 一个节目的分数不同。 1 <= n, x, y <= 1000 有难度，但是可以正好理解一下球盒问题。 x个节目可能不会用完 所以需要枚举选多少个节目，方案数应是所有方案之和。 枚举选择节目数\(m\) (1<=m<=x) 假设选择\(m\)个节目方案数为\(f[m]\)，则答案\(ans=\sum_{m=1}^{x}f[m]\) 对于选定的节目总数\(m\) 问题转换为\(n\)个球放进\(m\)个不同盒子中的方案数 若没有打分区别，易知\(f[m]=S(n,m)*m!\) 其中\(S(n,m)\)为第二类斯特林数 考虑打分的问题，已知选择了\(m\)个节目，每个节目可以打\([1,y]\)的得分，易知不同的组合为\(pow(y,m)\) 综上最终方案总数为\(ans = \sum_{m=1}^{x}S(n,m)*m!*pow(y,m)\) 注意取余处理。 完整代码略。 这个问题关键点在于理解。 为什么一个表演者在不同的节目中表演视为不同 是球不同盒不同盒不可以为空的模型？ 球不同盒相同的描述 表演者可以任意组合，如果存在一个表演者的组合不同视为不同活动 这意味着现实情形是 只有表演者们最终分组形式不同才是不同方案。 球相同盒不同的描述 存在一个节目的表演人数不同视为不同活动 显然，如果球相同(所有演员视为相同)，则一个节目中的表演人数发生变化 才能产生不同活动。 球相同盒相同 关键词：整数分拆 由于球盒均相同，比如3个球拆分为1+2和2+1是一个方案，区分不同方案本质只能把拆分序列升序排列，然后无法一一对应的序列才是不同的方案。 球相同盒相同，盒子可以为空 记 \(f(n,m)\)表示把 n 个相同球放进 m 个相同盒子，盒子可以为空的方案数 问题等价于方程式\(x_1+x_2+...x_m=n\)的非负整数解，但是要求\(x_1>=x_2>=...>=x_m\) 如果 \(n 依然是递推计算 \(f(i,j)\)，考虑 \(j\) 盒子是否为空 如果为空，则有 \(f(i,j)=f(i,j−1)\) 否则由于\(j\)不为空，则前面每个盒子必须都不为空。 每个盒子中放一个球，问题转换为 \(f(i,j)=f(i−j,j)\) 综上所述 \[f(n,m)=\begin{cases} 1&n=0 \\ 0&n>0,m=0 \\ f(n,n)&n f(n,m-1)+f(n-m,m)&n>=m \\ \end{cases} \] //空间优化的动态规划求解 //n个相同球放入m个相同盒子的不同方案数 //或者把整数n拆分为m个非负整数的方案数 int countPartitions(int n, int m) { vector f[0] = 1; for (int i = 1; i <= m; i++) { for (int j = i; j <= n; j++) { //正序，因为递推式里是当前轮的f[j-i] f[j] += f[j - i]; } } return f[n]; } 球相同盒相同，盒子不可以为空 把每个盒子先放一个球进去，问题转换为 \(n−m\) 个球放进 \(m\)个盒子，盒子可以为空的方案数 所以 \(f'(n,m)=f(n−m,m)\) 注意必须 \(n>=m\)