第一次认真算宝石装箱的时候我犯了个很低级的错误题干说 n 颗宝石放进 m 个盒子我上来就写 m 的 n 次方。等自己验数据 n3、m2 时m^n8手写枚举却只有 6 种怎么都对不上。后来才反应过来题目藏在“每个盒子不能空”这句话里。宝石装箱容斥原理这一系列问题说难不难可一旦把容斥公式的符号记错结果会错得相当离谱。这篇文章就以最标准的模型为主线n 颗互不相同的宝石m 个互不相同的盒子每个盒子至少放一颗问一共有多少种放法。我会从公式推导讲到数值验证再讲到代码实现和常见变体。无论你是刚开始学组合计数还是做算法题时被这类问题折磨过应该都能从这里直接找到能用的结论。1. 宝石装箱问题的标准模型与朴素方案的盲区1.1 先把“有区别”和“没有区别”分清楚宝石装箱题刚上手时最容易忽略的是对象是否有区别。我工作里遇到过有人把“盒子没有编号”和“盒子有编号”混在一起算最后答案差了 m! 倍还浑然不知。所以第一步永远是确认宝石之间能不能分出来盒子之间能不能分出来默认讨论的是最经典的一类n 颗宝石互不相同比如红宝石 1 号、蓝宝石 2 号、祖母绿 3 号……颗颗都能辨认m 个盒子也互不相同记为盒子 1、盒子 2……盒子 m。这时每一颗宝石选择哪个盒子本质上就是一个“从宝石集合到盒子集合”的函数。如果允许空盒答案就是 m^n宝石 1 有 m 种选择宝石 2 也有 m 种选择选择之间相互独立直接相乘。麻烦出在“每个盒子至少一颗宝石”。加上这个限制后计数对象就从“任意函数”变成了“满射函数”每个盒子都必须被至少一颗宝石命中不允许落空。这里先给一个实用的判断口诀拿到题先看 n 和 m 的大小。如果 n m根本不可能做到每个盒子都非空答案是 0直接收工。如果 n m那每个盒子刚好只能分到一颗宝石答案就是 m 的阶乘。这两条边界在调试时极其好用后面代码部分还会再说一遍。1.2 直接数“装满”为什么容易算乱有人可能会想既然不能空盒那我把 n 颗宝石先拆成 m 堆再给堆标上盒子号不就是答案吗方向没错但执行起来立刻撞上一个大坑拆堆的方式本身极难数清楚。拿 n5、m3 来说5 颗宝石只能拆成 (3,1,1) 或 (2,2,1) 两种各盒数量分布。可“哪三颗在一堆”和“哪两颗在一堆”的组合有很多种堆与堆之间谁对应哪个盒子又会产生排列。如果先拆堆再分配盒子每一步都可能把同一份最终方案重复算好几遍。更隐蔽的错误发生在“枚举每个盒子放哪些宝石”时。初学者喜欢从第一个盒子开始枚举集合再枚举第二个盒子最后检查有没有空盒。逻辑上没问题但状态会指数膨胀第一个盒子可以选 2^n 种子集第二个盒子又要从剩余宝石里选层数一多循环根本写不完。朴素做法的复杂度几乎就是 O(m^n)n 稍微大一点就跑不动。所以这类题的通用解法不是正向构造而是反向剔除先把“可以空盒”的全集算出来再把“至少有一个盒子空着”的方案从全集中减掉。这个剔除过程正是容斥原理最擅长的场景。2. 容斥原理如何从全集中剔除“空盒子事件”2.1 把“有空盒”翻译成事件的并设全集 U 是允许空盒的全部方案大小是 m^n。记事件 E_i 表示“第 i 个盒子里一颗宝石都没有”。那么只要方案中存在任何一个空盒它就落在 E_1 ∪ E_2 ∪ … ∪ E_m 这个并集里。题目要求“没有空盒”答案就是|U| - |E_1 ∪ E_2 ∪ … ∪ E_m|直接算并集的大小很痛苦因为事件之间大量重叠同一个方案可能让盒子 1 和盒子 2 同时是空的。容斥原理处理重叠的方式是反过来按“交集大小”逐层加加减减先统计“单个盒子为空”的和减去“两个盒子同时为空”的和再加上“三个盒子同时为空”的和如此反复。提示容斥公式里的求和从 k0 开始k0 那一项就是全集 U是整个式子的起点。后面 k1 开始才真正进入“剔除”。2.2 任意指定 k 个空盒计数非常容易容斥在这个问题里好用核心原因是“指定某些盒子为空”这件事意外地好算。假设我现在强制让 k 个盒子全空那这 k 个盒子就像上了锁所有宝石都不能放进去。剩下的 m-k 个盒子可以随意接收宝石所以每颗宝石只有 m-k 种选择n 颗宝石一共就是 (m-k)^n 种方案。再乘上选盒子的方式从 m 个盒子中挑出哪 k 个是空的有 C(m,k) 种选法。于是“至少这 k 个指定的盒子为空”的方案总数是C(m,k) × (m-k)^n注意这里说的是“指定这 k 个为空”不是“恰好只有这 k 个为空”。其他没被指定的盒子也可能恰好真空了这没关系容斥原理要的正是这种带重叠的“至少”型计数也就是交集 |E_{i1} ∩ E_{i2} ∩ … ∩ E_{ik}| 的总和。2.3 一正一负的符号是怎么定下来的容斥原理的经典形式是多个事件并集的大小等于“单个事件之和”减去“两两交集之和”加上“三三交集之和”一直交替到全部交。应用到空盒事件上最终公式是f(n,m) Σ_{k0}^{m} (-1)^k C(m,k) (m-k)^n展开写就是k0m^n所有方案全算进去k1减去 C(m,1)(m-1)^n去掉“至少一个盒子为空”的部分k2加上 C(m,2)(m-2)^n把刚才多减的“两个盒子同时为空”补回来k3再减去 C(m,3)(m-3)^n因为三个盒子同时为空又被加多了一直交替到 km。所以符号交替不是拍脑袋定的而是推导“全集减并集”时自然带出来的。很多人背公式时容易记反但只要心里装着“减掉并集”这个过程符号就再也不会弄错。2.4 宝石装箱其实就是“满射计数”从另一个角度看这套公式还有一个非常漂亮的对应关系每个宝石选盒子的方案就是一个从 n 元集合到 m 元集合的函数“每个盒子至少一颗宝石”就是满射条件。组合数学中满射的个数恰好是 m! × S(n,m)其中 S(n,m) 是第二类斯特林数。那 m! 从哪来可以理解成先把 n 颗宝石分成 m 个非空的类每类再对应一个盒子。非空分类的方式数是 S(n,m)每类分配给哪个具体盒子再乘 m!两个层次恰好拆开了。把这两个视角拼在一起你会得到一个重要信心不管题目包装成“宝石装箱”“信件投筒”“糖果分罐”还是“任务分配给处理器”只要本质是“每个桶至少一个对象”公式都长一个样。做题时就不容易被表面的故事迷惑。3. 数值验证与程序实现3.1 手工算一遍 n5、m3公式不能光背要亲手算一遍才有感觉。代入 n5、m3k0C(3,0)×3^5 243k1-C(3,1)×2^5 -3×32 -96k2C(3,2)×1^5 3×1 3k3-C(3,3)×0^5 0n0 时 0 的 5 次方就是 0合计 243-963150。这个数不是凭空冒出来的可以用最笨的枚举法验证。5 颗宝石放进 A、B、C 三个盒子每个盒子非空数量分布只有两类一个盒子 3 颗、另两个盒子各 1 颗或者一个盒子 1 颗、另两个盒子各 2 颗。先看 (3,1,1)选出拿 3 颗的盒子3 种从 5 颗宝石里选 3 颗给它C(5,3)10 种剩下两颗分别给另两个有编号的盒子2 种排列。所以是 3×10×260。再看 (1,2,2)选出只拿 1 颗的盒子3 种从 5 颗里选 1 颗给它5 种剩下 4 颗分成两组各 2 颗给剩余两个有编号的盒子C(4,2)6 种。所以是 3×5×690。6090150和容斥公式完全一致。这个手工验证过程强烈建议自己走一遍能极大降低对公式的怀疑。3.2 边界条件的验证表写代码之前先列几个边界值后面当断言用输入期望结果为什么n1, m11颗唯一的宝石塞进唯一的盒子n3, m262^3-2每个盒子非空只有 6 种n4, m4244!每个盒子恰好一颗n2, m30宝石不够填满所有盒子n5, m3150上面刚手算过这几个数一旦对不上说明公式或代码里大概率有符号错误、组合数算错或幂算错。3.3 Python公式版与 DP 版互相验证公式版代码很直接。Python 的整数是任意精度的n 再大也不怕溢出from math import comb def count_no_empty_box(n: int, m: int) - int: n颗互不相同宝石放入m个互不相同盒子每个盒子至少一颗。 if n m: return 0 ans 0 for k in range(m 1): term comb(m, k) * (m - k) ** n ans term if k % 2 0 else -term return ans光有公式还不够万一公式里的组合数或者幂写错了呢所以我通常还会写一个动态规划版来交叉验证def count_no_empty_box_dp(n: int, m: int) - int: dp [[0] * (m 1) for _ in range(n 1)] dp[0][0] 1 for i in range(1, n 1): for j in range(1, min(i, m) 1): dp[i][j] j * (dp[i - 1][j] dp[i - 1][j - 1]) return dp[n][m]这个 DP 的含义是dp[i][j] 表示前 i 颗宝石放进 j 个有编号盒子的非空方案数。转移时第 i 颗宝石要么插进已有 j 个盒子中的某一个因为第 i 颗宝石是新增的对象不能让某个盒子白拿所以前 i-1 颗已经让 j 个盒子都非空因子是 j要么第 i 颗宝石自己单独占据一个之前完全空的盒子前 i-1 颗已经铺满 j-1 个盒子而这个独立的新盒子有 j 个标签可选因子同样是 j。两者合起来就是上面的递推式。用 n5、m3 分别跑两个函数都会得到 150。这样交叉验证之后才敢把公式往其他数据上套。4. 扩展无标号盒子、禁放限制和其他变体4.1 盒子完全相同时除以 m! 是有条件的如果题目把盒子改成完全相同的所有盒子没有标签那每个“带标签盒子方案”恰好对应 m! 种带标签的排列方案。于是无标号盒子的答案就是S(n,m) f(n,m) / m!例如 n5、m3带标号答案是 150除以 3!6 得到 25。这个 25 对应第二类斯特林数 S(5,3)。注意不要在任何情况都无脑除以 m!。如果问题额外加了“某颗宝石不能进某类盒子”这类禁放规则禁放条件会打破盒子之间的对称性。此时先算带标号答案再除以 m! 是错的因为被禁止的方案在不同标签排列下分布并不均匀。很多人处理混合变体时就在这里翻车我见过不止一次。4.2 带禁放限制时容斥还能怎么用举个例子假设有 3 颗宝石 R、B、G两个盒子 A、B要求两个盒子都非空同时 R 不能放进 BB 不能放进 A。直接枚举也很简单。R 只能放 AB 只能放 BG 可以放任意一个盒子。所以合法方案只有两个G 放 A或者 G 放 B。但如果用容斥视角看过程是在不考虑禁放时3 颗宝石放 2 个盒子的非空方案是 2^3-26。再删掉违反禁放的方案。“R 放了 B”的方案数R 固定在 BG 和 B这里指宝石 B任意放 A/B共 3 种“宝石 B 放了 A”的方案数也是 3 种。两个条件同时违反要求 R 在 B 且 B 在 A剩下 G 任意放共 2 种。所以合法数为 6-3-322。这种“禁放事件”也可以用容斥公式扩展只是每一项的计数不再像“空盒”那样整齐需要按具体规则重新算交集。一般建议禁放条件少时手动容斥很直观禁放条件多时直接上状态压缩 DP 更省心。4.3 从宝石装箱伸向更广的场景这套计数模型在真实场景里其实经常出现。比如把不同任务分配给若干台处理器要求每台处理器至少分到一个任务把商品分成几组上架要求每组至少有一件甚至可以把数据划分到多个缓存桶要求每个桶都不能空。识别“每个桶至少一个对象”这个骨架比记住具体题目重要得多。如果你需要一次性算很多不同的 n进阶一点可以借助生成函数f(n,m) 对应的指数型生成函数是 (e^x - 1)^m。展开后取 n 次项系数再乘 n!就得到答案。这条路线在求斯特林数整行时非常有用不过日常做题用不上那么深知道有这条路就行。5. 实际编码与踩坑细节5.1 先处理边界别再让公式白跑写代码的第一行就应该把 n m 的情况拦下来。公式本身也能算出 0因为某些项会相互抵消但算了半天最后得 0 既浪费又容易让人怀疑自己写错了不如提前返回。对于 n0 这种极端值行业内比较通用的约定是n0, m0算 1表示“没有宝石也没有盒子”这一种空方案n0, m0算 0因为你不可能让非空盒子装满空气。DP 初始化时 dp[0][0]1 最顺后续转移不会出问题。不同题目可能有自己的约定但有了这个参考系至少能快速定位问题。5.2 大整数与取模三个容易致命的小细节第一如果要用精确整数语言必须支持大整数。用 C 的 int 或 long long 时n30、m15 就已经快爆了Python 虽然天然任意精度但如果换成其他语言就需要 BigInteger 或直接走取模路线。第二取模时负号是真坑。容斥公式里符号一正一负如果在 C 里直接取模负数会保留负号得到错误结果。通用做法是每一步都对模数取正MOD 1_000_000_007 def surjective_count_mod(n: int, m: int) - int: if n m: return 0 ans 0 for k in range(m 1): term comb(m, k) * pow(m - k, n, MOD) % MOD if k 1: ans (ans - term) % MOD else: ans (ans term) % MOD return ans第三组合数 C(m,k) 如果 m 很大不能每次都现场从 1 乘到 k。高效做法是预计算 0 到 m 的阶乘和逆元或者直接用累乘递推式 C(m,k)C(m,k-1)×(m-k1)//k。小规模无所谓规模上去了性能差距非常明显。5.3 调试用的“三板斧”我自己的调试习惯是写完公式后立刻跑三组最便宜的用例第一组 m1任何 n≥1 结果都应该是 1如果算出来不是 1说明幂或项数出问题了。第二组 nm结果应该是 m!例如 f(4,4)24这是检验容斥符号最锋利的用例。第三组 n3, m2结果应该是 6而不是 8。8 是忘了“不允许空盒”时的错误答案。这三组用例一分钟就能跑完却能把绝大多数“组合数写错”“符号写反”“幂底数写错”的问题直接暴露出来。我每次写完这类代码都会先过一遍确认无误之后再处理大数据。另外关于 0^n 这种项我也提醒一句在 n0 时 0^n0所以当 m-k0 时这项可以直接忽略但如果 n00^0 在组合数学里一般按 1 处理很多语言在这块的行为并不一致最好在代码里显式规避而不是依赖语言默认行为。写到这里把最后一个我特别喜欢的检查技巧分享出来当我不确定容斥公式到底该用哪一版时我从不直接上大数验证而是在纸上先写 n3、m2 的枚举3 颗宝石放进 A、B 两个盒子每个盒子非空总共 6 种。然后把 6 带进公式看正负符号对不对。只要符号有问题这一组用例会立刻暴露出差异。宝石装箱这类题的难点从来不在“算 m^n”而在“不许空盒”这层约束容斥最大的价值就是把这句“不许”翻译成了“全集减事件并”剩下的无非是耐心拆项。希望这篇文章能让你和我一样下次再看到这类题时第一反应不再是硬枚举而是稳稳地写出那行求和式。