看到“宝石装箱（容斥原理）”这个标题，估计不少刷组合计数题目的朋友会心一笑：这几乎是容斥原理最经典的落地场景之一。宝石有不同颜色、每种颜色有若干颗，箱子各不相同，最后还要求每个箱子都不能空——正面硬算基本没法下手，但一旦想到“先随便放，再把某些箱子空着的情况剔除”，整个问题就变得异常清晰。
这篇文章会从问题建模开始，把容斥原理的推导过程、隔板法的正确用法、组合数预处理的细节、代码实现一步步写清楚，再附上几个典型变体和我的踩坑记录。不管你是刚接触计数题的新手，还是想系统整理容斥用法的老手，这篇应该都能给你一些可以直接抄作业的东西。
1. 先把问题说清楚：宝石装箱到底在“装”什么
我最初接触这类问题时的设定是这样的：有 n 种宝石，第 i 种宝石有 a_i 颗，同一颜色宝石之间不可区分；有 m 个互不相同的箱子，要求把所有宝石全部装箱，并且每个箱子最终至少要有一颗宝石。问有多少种装箱方案。
这里有几个关键字值得先拆一下：
- 每种宝石有固定数量：比如红色 2 颗、蓝色 3 颗，这些宝石除了颜色以外不能靠编号区分。也就是说，红色第 1 颗和红色第 2 颗互换位置，在计数时不产生新方案。
- 箱子互不相同：箱 1 和箱 2 是两个独立个体，宝石放进箱 1 还是箱 2 是两种不同方案。
- 每个箱子非空：这是题目里最扎人的约束。如果没有这个约束，方案数会非常容易算——每种颜色独立做隔板法然后相乘就行。一旦加上“非空”，就必须想办法处理“某个箱子一个宝石都没有”的情况。
顺带说一句，有些变体里宝石是每颗都不同的（带编号），那种情况更简单，我后面会专门给公式。本文默认先处理“同色宝石不可区分”的版本，因为它更能体现容斥原理和隔板法配合的完整思路。
这个问题的规模一般不大，n 和 m 通常在几千到几万之间，a_i 的总和可能在十万级，要求输出对某个质数（比如 1000000007）取模的结果。这种规模下，我们需要一个 O(nm) 甚至更优的算法，不能靠暴力枚举宝石分配。
为什么这个题适合拿来学容斥？因为它把“每个箱子非空”翻译成“不存在空箱子”，而“不存在”恰好是容斥原理的主场。后面我会详细讲这个翻译过程。
2. 容斥原理的核心动作：把“每个箱子都不空”反过来数
2.1 从抛硬币类比说起
想象你给 m 个朋友发宝石，要求每个人都必须收到至少一颗。直接统计“每个人都收到”的方案数很困难，因为你没法枚举“谁收到了哪些宝石”再判断是否有人没收到。
换一个思路：先让宝石随便发，不管朋友有没有收到。这时候方案总数是很好算的。但这里面混入了“有人没收到”的情况。于是问题变成：从“随便发”的总数里，去掉“至少有一个人没收到”的方案。
问题在于，“至少有一个人没收到”这个事件是并集，直接统计并集也不容易。但容斥原理告诉我们，一个并集的大小可以拆成所有交集的组合数加减：
| U_{i=1}^{m} A_i | = Σ |A_i| − Σ |A_i ∩ A_j| + Σ |A_i ∩ A_j ∩ A_k| − …
在这里，A_i 就代表“第 i 个箱子是空的”。那么：
- 求所有 A_i 都不发生，等价于全集减去这些 A_i 的并集。
- 而并集里的每一项，比如 A_1 ∩ A_2，意思是“1 号箱和 2 号箱同时为空”，这样一个交集只需要把宝石限制到剩下的 m−2 个箱子里分配，计算难度大大下降。
这就是容斥原理在本题里真正承担的任务：把一组复杂的全体约束，拆成一系列简单的“指定某些箱子为空”的子问题。
2.2 字母公式与符号约定
设全集 U 是所有宝石任意放入 m 个箱子的方案集合。“第 i 个箱子为空”记为事件 A_i。
我们要的数量是：
ans = |{方案：所有箱子都非空}| = |U| − |∪_{i=1}^{m} A_i|
容斥展开后得到：
ans = Σ_{S ⊆ {1,…,m}} (−1)^{|S|} × N(S)
其中 N(S) 表示“S 中所有箱子都为空”时的方案数。
由于箱子本身互不相同，且事件只关心“哪些箱子空”，N(S) 只取决于 |S| = j，不取决于具体是哪 j 个箱子。于是可以把相同 j 合并，得到：
ans = Σ_{j=0}^{m} (−1)^j × C(m, j) × F(m − j)
这里 F(k) 表示：所有宝石只能放入指定的 k 个箱子（可空）时的方案数。这个式子里每一项的 C(m, j) 就是在挑选“哪 j 个箱子被迫为空”。
提示：这个合并技巧非常常用。只要子问题结果只和集合大小有关，就可以直接用组合数合并，而不是枚举 2^m 个子集。这道题本质就是用这个性质把指数级枚举打成了多项式级。
2.3 为什么非用容斥不可
有人可能会问：能不能枚举每个箱子放多少颗宝石，再用组合数分配颜色？对于小规模可以，但一旦宝石总数上万、箱子数上百，状态空间就爆炸了。
还有一个常见的朴素想法：先把 m 颗宝石拿出来每个箱子放一颗，再分配剩下的宝石。问题是宝石带有颜色，先拿哪一颗会影响后续计数，而且同颜色宝石之间不可区分，这种“先占位再分配”的做法很容易重复计数或遗漏。
容斥的优势在于：它把问题切成了 m+1 个互相独立、结构相同的子问题。每个子问题只需要做一次“可空箱子”的计数，而这一步是简单的隔板法。这种“把不可行的整体约束，转化成若干可行的子约束”的思想，是很多计数题的通用解法。
3. 可空箱子下的计数：隔板法才是真正的前置技能
3.1 一种颜色一颗一发？
现在考虑子问题 F(k)：有 k 个箱子，所有宝石可以任意放进去，箱子可空。宝石按颜色分成 n 组，每组 a_i 颗，同一颜色不可区分。
因为不同颜色之间互相独立——红色怎么放不影响蓝色的放法——所以 F(k) 就是每种颜色的方案数相乘：
F(k) = ∏_{i=1}^{n} g(a_i, k)
其中 g(a, k) 表示把 a 颗同色球放入 k 个不同箱子（允许空箱）的方案数。
g(a, k) 就是经典的隔板法：a 个球排成一列，中间有 a−1 个空隙，插入 k−1 块隔板，把球分成 k 段，依次对应箱 1 到箱 k。因为允许空箱，可以把隔板允许相邻，甚至放在最左和最右，这样等价于从 a + k − 1 个位置里选 k − 1 个位置放隔板，即：
g(a, k) = C(a + k − 1, k − 1)
用一个简单例子验证：a = 1, k = 2，C(1 + 2 − 1, 1) = C(2, 1) = 2。这一颗球可以放箱 1 或箱 2，两种方案，正确。
再验证 a = 2, k = 3，C(2 + 3 − 1, 2) = C(4, 2) = 6。手动枚举：2 颗同色球放 3 个箱，可能是一个箱子放 2 颗（3 种），也可能是两个箱子各放 1 颗（C(3,2)=3 种），总共 6 种，正确。
3.2 组合公式 F(k) 的完整形式
把每种颜色的隔板法结果乘起来：
F(k) = ∏_{i=1}^{n} C(a_i + k − 1, k − 1)
于是最终的容斥公式可以写成：
ans = Σ_{j=0}^{m} (−1)^j C(m, j) ∏_{i=1}^{n} C(a_i + m − j − 1, m − j − 1)
这就是整道题的核心公式。
注意一个边界：当 j = m 时，k = 0。此时如果把 k−1 = −1 套进组合数会出错。但只要宝石总量非零，0 个箱子根本装不下任何宝石，F(0) 应该直接取 0。具体代码里我建议对 k = 0 单独判断，而不是依赖组合数函数的边界行为。
3.3 另一种情况：宝石全部不同
如果题目改一下，每颗宝石都有唯一编号（即全部宝石互不相同），那么 F(k) 就更好算了：每一颗宝石都可以独立选择 k 个箱子之一，所以 F(k) = k^N，其中 N = Σ a_i。
容斥公式变成：
ans = Σ_{j=0}^{m} (−1)^j C(m, j) (m − j)^N
这和第二类斯特林数有直接关系：m! × S(N, m) = Σ_{j=0}^{m} (−1)^j C(m, j) (m − j)^N。
所以如果你只是想把 N 个不同物品分到 m 个非空不同箱子里，上面的公式其实就是标准答案。我建议把这两种情形分开记忆：同色宝石用隔板法，不同宝石用幂函数，两者看似相近，但隔板法那步很容易被记错。
4. 完整推导演示：从全集到每个子项
这部分我用一个具体例子把公式从头到尾走一遍，方便你对照理解。
设 n = 2，a = [1, 2]，m = 2。也就是红色 1 颗，蓝色 2 颗，两个箱子 A、B，要求两个箱子都不为空。
第一步，枚举 j：
- j = 0：表示没有强制空箱，F(2) = C(1+2−1, 1) × C(2+2−1, 1) = C(2,1) × C(3,1) = 2 × 3 = 6。
- j = 1：表示有 1 个箱子被迫为空，剩下 1 个箱子可空。F(1) = C(1+0, 0) × C(2+0, 0) = 1。
- j = 2：剩下 0 个箱子，宝石总数为 3，F(0) = 0。
第二步，代入容斥公式：
ans = C(2,0)×6 − C(2,1)×1 + C(2,2)×0 = 6 − 2 = 4
手动验证：红色宝石和蓝色宝石共 3 颗，要分到 2 个箱子且都非空。由于红色只有 1 颗，红色必须在某个箱子；蓝色 2 颗同色不可区分。
方案其实就两类：红色在箱 A，那蓝色至少 1 颗在箱 B，且剩余蓝色可以任意。蓝球 2 颗可分给 A、B，但不允许全在 A（这样 B 没有蓝球且红在 A 导致 B 空）。所以合法分配为：蓝球在 B 有 1 颗或 2 颗，共 2 种。对称地，红在箱 B 时也是 2 种。总共 4 种。公式结果正确。
再验证一个更简单的情况：a = [1, 1]，m = 1。只有 1 个箱子，两颗不同颜色宝石都要放进去，方案只有 1。
公式：j=0 时 F(1) = 1×1=1；j=1 时 F(0)=0。ans = 1。正确。
这种小数据验算是我强烈推荐的做题习惯。公式推导完先别急着写完整代码，用两三组极端数据手算一遍，能提前抓住很多下标和符号错误。
5. 代码实现：Python 和 C++ 两个版本
5.1 Python 版本（无取模，便于理解）
先写一个不取模的版本，用 Python 内置组合数，方便在小数据上验证逻辑：
import math def solve_simple(a, m): n = len(a) total = sum(a) if total < m: return 0 if m == 0: return 1 if total == 0 else 0 ans = 0 for j in range(m + 1): k = m - j if k == 0: # 0 个箱子且宝石总数>0，不可能装下 ways = 0 else: ways = 1 for ai in a: ways *= math.comb(ai + k - 1, k - 1) term = math.comb(m, j) * ways if j % 2 == 0: ans += term else: ans -= term return ans print(solve_simple([1, 2], 2)) # 4 print(solve_simple([1, 1], 1)) # 1这个版本非常适合用来和后面的暴力算法对拍。它不用管取模，直接在整数上做，逻辑透明。
5.2 C++ 取模版本（竞赛向）
实际比赛中基本都要取模，所以需要预处理阶乘和逆元，用 O(1) 的组合数查询。
#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007LL; long long modpow(long long a, long long e) { long long r = 1; while (e) { if (e & 1) r = r * a % MOD; a = a * a % MOD; e >>= 1; } return r; } vector<long long> fact, invfact; void init_comb(int n) { fact.resize(n + 1); invfact.resize(n + 1); fact[0] = 1; for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD; invfact[n] = modpow(fact[n], MOD - 2); for (int i = n - 1; i >= 0; i--) invfact[i] = invfact[i + 1] * (i + 1) % MOD; } long long C(int n, int k) { if (k < 0 || k > n) return 0; return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD; } long long solve(vector<int>& a, int m) { int total = accumulate(a.begin(), a.end(), 0); if (total < m) return 0; if (m == 0) return total == 0 ? 1 : 0; // 组合数参数最大不会超过 max(total + m, m) init_comb(total + m + 5); long long ans = 0; for (int j = 0; j <= m; j++) { int k = m - j; if (k == 0) continue; // 宝石总数非0，F(0)=0 long long ways = 1; for (int ai : a) { ways = ways * C(ai + k - 1, k - 1) % MOD; } long long term = C(m, j) * ways % MOD; if (j & 1) ans = (ans - term + MOD) % MOD; else ans = (ans + term) % MOD; } return ans; } int main() { vector<int> a = {1, 2}; cout << solve(a, 2) << "\n"; // 4 return 0; }几个实现要点：
- 初始化组合数时，上限取
total + m + 5是因为 C(a_i + k - 1, k - 1) 里的 a_i + k − 1，最大的可能就是某个 a_i 等于 total，且 k = m，所以 total + m 一定够用，再多加 5 防止手滑。 - 枚举 j 的时候，及时
continue掉 k = 0 的情况。否则 C(ai - 1, -1) 在部分实现里会返回 0，其实结果没错，但依赖了组合数函数的容错行为，不够严谨。 - 取模减法先加 MOD 再取模，避免负数。
- 时间复杂度 O(nm)，空间 O(total + m)。对于 n,m 在几千级别的数据，这个算法非常稳定。
6. 变体扩展：一个公式是怎么长出很多花样的
6.1 变体一：每颗宝石都有编号
如果宝石全部不同，F(k) = k^{total}，代码里把隔板法替换成快速幂即可。这个变体的好处是复杂度还能进一步优化，因为只需要对每个 j 算一个幂，不能算什么大挑战。
公式：
ans = Σ_{j=0}^{m} (−1)^j C(m, j) (m − j)^{total}
这个式子也是第二类斯特林数和排列组合的结合点，适合当作“容斥入门后的进阶思考题”。
6.2 变体二：某些颜色不能放进同一个箱子
假设题面加了一条：第 1 种颜色和第 2 种颜色的宝石不能出现在同一个箱子里。怎么处理？
一个很妙的转化是：把“不能同箱”的两种颜色临时合并成一种“超级宝石”，然后统计所有装箱方案，再减去“它们同箱”的方案。具体做法是：
- 定义事件 B = “颜色 1 和颜色 2 至少在一箱中共存”。
- 求 |B| 时，把颜色 1 和颜色 2 的宝石合并成一组，数量为 a_1 + a_2，重新套用原公式算所有箱子非空的方案，这正好对应“两种颜色至少某箱同箱”的方案数（因为合并后它们就必然属于同一个箱子组合）。
- 最后用全集方案数减去 |B|。
注意，这里要小心重复减去：如果两种颜色在多个箱子里都共存，合并后只算一次，所以直接用全集减去合并方案是正确的。
这种“合并对象再容斥”的小技巧，在染色和装箱类题目里经常出现，学会一个可以迁移到很多场景。
6.3 变体三：每个箱子至少 k 颗宝石
当约束从“非空”变成“至少 k 颗”，直接用容斥的复杂度会急剧上升，因为事件变成“第 i 个箱子宝石数 ≤ k−1”，而这样的交集计数没法只靠隔板法解决。
更实用的思路是：
- 如果宝石互不相同，可以先把 k 颗宝石视为每个箱子的“基础配额”，发现不好处理；此时生成函数或动态规划更合适。
- 如果宝石同色且每种数量不大，可以考虑对每种颜色的分配做卷积，最终统计每个箱子容量 ≥ k 的方案数。
提这个变体是想提醒你：容斥不是万能的，它的威力在于处理“某个对象被完全排除”这类二元事件。一旦约束变成程度的限制（至少多少颗、不超过多少颗），就要考虑动态规划、生成函数等其他工具。做题时先分层，不是所有计数题都该硬上容斥。
6.4 变体四：箱子数量非常大，但宝石种数很少
如果 n 很小、m 高达 1e7，O(nm) 依然不可行。这时候可以换个观察角度：容斥公式里每个子项的 F(k) 是关于 k 的多项式函数，因为 C(a_i + k − 1, k − 1) 是关于 k 的 a_i−1 次多项式。整个 ans 是这些多项式乘积的线性组合，阶数不超过总数 N。于是可以：
- 用拉格朗日插值计算 m 处的值；
- 或者直接以求和的形式推导成伯努利数相关的公式。
这个话题就有点深了，适合在掌握了基础版本之后自行探索。知道有这个方向就行，至少遇到超大 m 时不会一头雾水。
7. 实战中的坑：我从这类题身上踩过的雷
7.1 坑一：隔板法公式记错
最容易记错的点是 C(a + k − 1, k − 1) 还是 C(a + k, k)。我的记忆方法是：a 颗球放 k 个盒子允许空盒，等价于 a 个球和 k−1 个板共 a+k−1 个位置里选 k−1 个放板。只要记住“板比盒子少一块”，就不会写错。
7.2 坑二：k=0 被组合数函数吞掉
很多组合数模板里，C(n, −1) 直接返回 0，于是 k=0 时 ways 也会变成 0，最终公式看起来没错。但如果你换了模板，或者用 Python 的 math.comb，C(ai−1, −1) 会直接抛异常。所以比较稳的是在枚举循环里显式判断 k == 0，不要依赖底层函数的容错。
7.3 坑三：组合数预处理范围不够
我见过有人只初始化到 n+m，结果调用 C(ai + k − 1, k − 1) 时下标越界。稳妥做法是初始化到 total + m + 5。特别是当 a_i 的总和很大时，一定要记得把total加进上限。否则程序跑起来没报错但结果错乱，非常难查。
7.4 坑四：总宝石数小于 m 时直接忽略
如果宝石总数小于箱子数，方案一定是 0。这个特判虽然简单，但很容易被漏掉。漏掉之后容斥公式也会给出 0，因为数学上恒等式成立，但中间可能涉及大量无意义的组合数计算，甚至溢出。先特判，既提高速度也避免边界风险。
7.5 坑五：暴力对拍时把“同色宝石”当成可区分的
写暴力验证时，最容易出现的逻辑谬误是枚举宝石编号而不是颜色分配。同色宝石不能区分，所以暴力应当枚举“每种颜色在每个箱子里的数量”，而不是“每颗宝石去哪个箱子”。后者会把方案数放大很多。
我常用的暴力框架是这样的：
def brute(a, m): total = sum(a) if total < m: return 0 ans = 0 def dfs(idx, empty_mask): nonlocal ans if idx == len(a): if empty_mask == (1 << m) - 1: ans += 1 return ai = a[idx] # 枚举第 idx 种颜色在 m 个箱子中的数量分配 def distribute(rem, box, cur): nonlocal empty_mask # 这里在嵌套函数中要用 nonlocal if box == m - 1: new_empty = empty_mask if rem > 0: new_empty |= (1 << box) # 修正之前的空箱标记 for b in range(m): if b < box and cur[b] > 0: new_empty |= (1 << b) dfs(idx + 1, new_empty) return for take in range(rem + 1): if take > 0: empty_mask |= (1 << box) distribute(rem - take, box + 1, cur + [take]) if take > 0: empty_mask &= ~(1 << box) distribute(ai, 0, []) dfs(0, 0) return ans这个暴力只适合小数据，但它能帮你验证主算法的正确性。我用它对比过 a=[1,2,3]、m=3 等组数据，和容斥公式结果完全一致。强烈建议你在学新计数公式时，先写一个无脑暴力做对拍，Assert 通过后再提交主算法。
7.6 坑六：取模非质数
如果模数不是质数，预处理阶乘逆元的方法就不能用。此时要么用杨辉三角 O(N²) 预处理组合数，要么用扩展卢卡斯等更高级的工具。我建议写一个组合数类，内部判断模数是否为质数，选择策略，避免在题目模数变化时踩坑。
8. 个人体会：这类题到底在锻炼什么能力
宝石装箱这个模型，表面看是一个计数公式，但它的价值在于训练一种思维习惯：遇到“每个箱子都必须如何”的约束时，先不要急着正面构造，而是看看“指定一部分箱子不满足约束”能否变得可算。如果能，那容斥就是你的第一选择。
我个人的做题流程基本固定为四步：
- 形式化题目：明确哪些对象是可区分的，哪些是不可区分的，约束条件到底是什么。
- 选定容斥事件：事件要设计成“交集容易计数”的形式，而不是想当然地数“并集”。
- 写出通项公式：先对集合大小 S 表示出 N(S)，再尝试合并相同大小的子集。
- 小数据验证：用暴力或手算验几组边界，确认公式没错再写代码。
这套流程看着简单，但真到场上，很多人会在第二步卡住：事件选得不好，后面根本无法计数。宝石装箱就是练习“事件设计”的绝佳入门题，因为它的事件非常自然——某个箱子为空，交集就是“宝石只能放指定箱子”。
最后再说一个小技巧：当你把容斥公式里的 j 从 0 到 m 枚举时，可以顺手把每一项独立计算，不要试图合并同类项。这个公式本身已经是最优的 O(nm) 形态，合并反而容易搞乱符号。实际跑题时，直接把公式翻译成循环，是最不容易出错的做法。
希望这篇笔记能帮你把宝石装箱这条线彻底吃透。下次再看到“容斥原理”三个字，至少你能第一时间想到：先找一组好算交集的事件，再用组合数合并相同大小的子集，最后循环枚举符号就行。这个思维路径，会陪伴你走过很多看似复杂的计数题。
