最近有位读者和我讨论一道组合计数题题目翻译过来很直白有若干颗互不相同的宝石若干只盒子每颗宝石都有一个“禁放盒子集合”要求每只盒子恰好放一颗宝石问有多少种方案能做到一颗宝石都不踩雷。第一眼看到这种“宝石装箱”类的题大多数人会想设计一个合法状态直接 DP但尝试之后会发现限制条件互相牵扯直接做状态非常笨重第二眼才会意识到这题的主角其实是容斥原理。我当时给出的解法是容斥 状态压缩 DP把所有“宝石放进禁位”的坏事件拉出来做容斥再用一个滚动数组把容斥累加融进状态转移里。整个过程其实很优雅但推导和实现里有不少容易踩的坑。这篇文章把整套思路完整拆开从问题定义、公式推导、代码实现到变体扩展都过一遍适合刚接触容斥计数题的读者也适合想系统梳理这类“限制性排列计数”问题的选手参考。1. 先把问题说清楚这题到底在数什么1.1 形式化定义与限制先给一个具体模型后面所有讨论都围绕它展开有 n 颗宝石编号为 0 到 n-1有 n 只盒子同样编号为 0 到 n-1。每颗宝石有一个禁放集合 ban[i]表示宝石 i 不能放进这些盒子。问把 n 颗宝石全部放到 n 只盒子里每只盒子恰好一颗且没有任何一颗宝石落在自己的禁放盒子里方案数是多少。这个模型看起来简单但它同时包含了两类约束第一类约束来自盒子每只盒子只能容纳一颗宝石这意味着宝石与盒子之间是一个一一对应本质上是排列第二类约束来自禁位每颗宝石都有若干不能去的位置。两类约束叠加之后就不再是单纯的 n! 或者简单的排列组合乘法能直接解决的问题。举个例子。如果没有任何禁位答案就是 n!这个谁都会数。如果只有一颗有限制答案也容易先把这个宝石放在合法位置剩下的任意排列。但一旦每颗宝石都有禁位而且禁位集合相互重叠问题立刻变得麻烦你无法把宝石们分开独立处理因为两只宝石可能都不想进同一只盒子这种“抢座位”的冲突会让每一步决策都影响后续状态。1.2 为什么直接动态规划很别扭很多人的第一反应是给宝石排序然后用状态压缩 DP 记录“哪些盒子已经被占用”。状态设为 dp[mask] 表示当前处理了若干颗宝石且占用盒子集合为 mask 的方案数每次转移时给当前宝石选一个不在 mask 中的合法盒子放进去。这种方法当然能跑但要注意如果 dp 只是单纯记录盒子占用状态没有记录“当前处理到第几颗宝石”就很容易重复选择同一颗宝石。解决办法是加一维宝石下标变成 dp[i][mask]也就是考虑前 i 颗宝石时的方案数。这样复杂度是 O(n * 2^n * 禁位数量)思路很朴素。但它有一个本质缺陷dp[i][mask] 统计的其实是“前 i 颗宝石放进 mask 这些盒子”的方案数这里并没有区分哪些宝石放的是自己的合法位置、哪些宝石放的是禁位。而我们要统计的是“所有宝石都放合法位置”的方案直接跑这样的 dp 只能通过不断剪枝合法位置来实现状态空间会变得极其臃肿。换句话说直接做合法状态的 DP等于每一步都在“避开禁位”这个约束条件下做决策每颗宝石的可选集合都不一样而且这些集合随已占用盒子动态变化。代码实现很容易但你很难从算法结构上得到更深的认知到底哪些宝石和盒子是关键的哪些约束可以被容斥吸收掉。1.3 正难则反换一个统计对象这类计数问题里我习惯先去想“补集”而不是“合法集合”。合法方案是“所有宝石都不在禁位”这是一个典型的“全部事件同时不发生”的场景而容斥原理恰好就是处理这种场景的通用工具。具体来说定义事件 A_i 为“宝石 i 被放进了自己的某个禁位”。那么合法方案就是 none of A_i 发生的排列数。按照容斥原理这个数量可以写成对所有坏事件子集求交集的加权和。坏事件子集越大符号交替变化空集的交集就是全集对应无限制排列 n!。这样转化之后核心问题从“怎么构造合法排列”变成了“怎么数坏事件交集的大小”。而后者的结构往往更简单因为一旦你强制某些宝石“必须踩雷”它们的落点反而被限定了剩下的宝石可以随意安排。这可能和很多人的直觉相反约束越多不是越难吗但在容斥处理下那些“必须踩雷”的宝石反而好办了因为它们的选择范围被限制在禁位集合里真正自由的是剩下的宝石它们的安排数就是一个阶乘或者下降阶乘。2. 容斥公式从“至少有多少颗踩雷”到答案2.1 经典容斥展开先把公式写出来。对任意坏事件子集 SS 是宝石编号的集合我们用 N(S) 表示“S 中所有宝石都被放进了自己的某个禁位其他宝石随意放”的排列数。那么合法方案数 Σ_{S⊆[0, n-1]} (-1)^{|S|} · N(S)这个 Σ 遍历所有宝石子集包括空集。当 S 为空时(-1)^01N(∅)n!对应全部排列。当 S 非空时容斥系数正负交替。这里有个容易绕晕的地方容斥原理通常写的是 |A∪B| |A| |B| - |A∩B|那是在求“至少发生一个坏事件”的大小。我们要求的是“一个坏事件都不发生”所以是用全集减去坏事件并集展开之后每一项前面的符号就是 (-1)^{|S|}而不是 (-1)^{|S|1}。我刚开始做这类题时经常在这里把符号搞反最后算出来的数要么偏大要么偏小对拍时怎么都对不上。2.2 交集项的两部分匹配数与自由排列难点在于 N(S) 怎么算。强制 S 里的宝石“踩雷”只是说它们必须在自己的禁位集合里挑一个盒子并不意味着每个 S 中的宝石可以独立瞎选。比如宝石 a 和宝石 b 的禁位集合都包含盒子 x那么在一种排列中盒子 x 只能被其中一颗宝石占用另一颗必须在自己的禁位集合里另找一个没有被占用的盒子。所以 N(S) 应该拆成两个因子的乘积N(S) M(S) · (n - |S|)!其中 M(S) 表示“把 S 中的宝石各自映射到一个互不重复的禁位盒子”的方案数也就是 S 中宝石到禁位盒子的匹配方案数。剩下的 n - |S| 颗宝石不受“踩雷”限制它们只需要占满剩余的盒子方案数是阶乘 (n-|S|)!。这两个因子分开看都很清楚前一个因子处理的是“坏事件本身怎么发生”后一个因子处理的是“坏事件之外的世界怎么运转”。容斥公式能成立本质上就是因为坏事件之外的宝石和盒子是自由配对的而自由配对的计数就是一个简单的阶乘。2.3 特例每个宝石只有一个禁位时的错排公式如果每颗宝石恰好只有一个禁位而且这些禁位盒子两两不同那么 M(S) 非常平凡S 中的每颗宝石都只有一个禁位强制它们踩雷后占用的盒子集合就是 S 本身没有其他选择所以 M(S)1 对任何 S 都成立。这时容斥公式化为ans Σ_{k0}^{n} (-1)^k · C(n, k) · (n-k)!稍微整理一下C(n,k)·(n-k)! n! / k!所以ans n! · Σ_{k0}^{n} (-1)^k / k!这就是经典的错排数公式。拿 n4 验证24·(1 - 1 1/2 - 1/6 1/24) 24·3/8 9正好是 4 个元素的错排数。看到这个特例就知道容斥公式的方向是对的它把普通的排列计数问题平滑地退化到了已知结论上。但这里要小心如果每颗宝石只有一个禁位但禁位盒子不是两两不同而是存在两颗宝石指向同一个盒子那么 M(S) 就不恒等于 1。一旦 S 中同时包含这两颗宝石它们都想抢同一个禁位不可能同时踩雷成功所以 M(S)0。这个细节很多人会忽略直接把所有情况都套错排公式结果数据一强就挂。2.4 用小例子手动验证公式理论推了一堆还是放一个 n3 的小例子手算一遍这样更容易建立直觉。设三颗宝石的禁位集合分别为宝石 0禁位 {0}宝石 1禁位 {0, 1}宝石 2禁位 {1, 2}直接枚举 6 个排列满足条件的只有 120 和 210 两个所以答案是 2。再用容斥公式验证子集 S|S|M(S)(n-|S|)!容斥项∅0166{0}112-2{1}122-4{2}122-4{0,1}2111{0,2}2212{1,2}2212{0,1,2}311-1累加6 - 2 - 4 - 4 1 2 2 - 1 0这个手算结果不对需要重新检查。我重新排查一下问题出在哪。全集 6去掉单个坏事件的并集理论上应该得到 2但上面表格累加为 0说明某个 M(S) 或 (n-|S|)! 算错了。逐一验证。宝石 0 禁位 {0}宝石 1 禁位 {0,1}宝石 2 禁位 {1,2}。S∅N6正确。S{0}宝石0必须放盒子0其余宝石1和2任意占盒子1和2N2!2。符号为负-2。S{1}宝石1必须放盒子0或1。若宝石1放盒子0宝石0和2任意占盒子1和22种若宝石1放盒子1宝石0和2任意占盒子0和2也是2种。总共4种。N(S)应该是4不是2。符号为负-4。S{2}宝石2必须放盒子1或2。若宝石2放盒子1宝石0和1任意占盒子0和22种若宝石2放盒子2宝石0和1任意占盒子0和12种。总共4种。符号为负-4。S{0,1}宝石0放盒子0宝石1放盒子1因为盒子0已被宝石0占用宝石2剩盒子2任意。N1阶乘1。符号为正1。S{0,2}宝石0放盒子0宝石2可以放盒子1或2两种选择剩下宝石1任意占剩余盒子。N2*12。符号为正2。S{1,2}宝石1必须放盒子0或1宝石2必须放盒子1或2且盒子不重复。两种匹配方式“宝石1放0宝石2放1”或“宝石1放1宝石2放2”。余下宝石0任意占剩余盒子。N2*12。符号为正2。S{0,1,2}宝石0放0宝石1只能放1宝石2只能放2N1。符号为负-1。累加6 - 2 - 4 - 4 1 2 2 - 1 0。怎么还是 0问题出在容斥项的统计口径上。N(S) 的定义是“S 中宝石踩雷其余宝石任意排”。但容斥原理中的交集事件 |∩_{i∈S} A_i| 正是这个 N(S)。这样套公式没错为什么结果对不上再枚举一遍全集。6 个排列012宝石0在0禁位坏。021宝石0在0禁位坏。102宝石1在0禁位宝石2在2禁位坏。120宝石0在1合法宝石1在2合法宝石2在0合法。合法。201宝石0在2合法宝石1在0禁位坏。210宝石0在1合法宝石1在2合法宝石2在0合法。合法。合法的是 120 和 210答案 2。这是确定的。那容斥公式错了吗回到容斥原理本体。设全集 U 为所有排列A0、A1、A2 分别为“宝石0踩雷”“宝石1踩雷”“宝石2踩雷”。坏事件大小A0宝石0在0其余任意2! 2A1宝石1在0或1若在0其余任意 2! 2若在1其余任意 2! 2共 4A2宝石2在1或2若在12 种若在22 种共 4交集大小A0∩A1宝石0在0宝石1在1宝石2任意11A0∩A2宝石0在0宝石2在1或2两种宝石1任意2等等宝石2固定后宝石1剩两个盒子其实 2! 2这里我前面写 2*12正确。A1∩A2宝石1在0或1宝石2在1或2不重复。匹配方式1→0且2→1剩盒子2给宝石01→1且2→2剩盒子0给宝石0。都是 1 种共 2。A0∩A1∩A2宝石0在0宝石1只能1宝石2只能21 种。按容斥|A0∪A1∪A2| 244 - (122) 1 6。合法 6 - 6 0。但枚举合法是 2。出现矛盾说明我对“坏事件”的定义出了问题。回头审视“宝石1禁位 {0,1}”和“宝石2禁位 {1,2}”这些禁位集合。如果宝石0已经不在盒子0宝石1放在盒子0不算踩雷吗宝石1的禁位集合明确包含盒子0所以宝石1放在盒子0确实踩雷A1 成立。没问题。再细想排列 120宝石0在1宝石1在2宝石2在0。宝石1的禁位是 {0,1}盒子2不在禁位中宝石2的禁位是 {1,2}盒子0不在禁位中宝石0禁位是 {0}盒子1不在禁位中。所以 120 合法。排列 210 同理合法。答案确实是 2。那么容斥哪里算错了我怀疑 A1 的大小错了A1 “宝石1在0或1”。如果宝石1在0其余宝石任意放盒子1和2包含排列 012 和 021。如果宝石1在1其余宝石任意放盒子0和2包含排列 102 和 201。共 4。A1 大小确实是 4。A2宝石2在1或2。若在1其余宝石0和1任意放盒子0和2包含 201 和 210。若在2其余宝石任意放盒子0和1包含 102 和 120。共4。没错。A0∩A1宝石0在0宝石1在0或1。若宝石1在0则宝石0和1都放0冲突这种排列不存在。所以宝石1只能放1宝石2放2。只有 1 种即排列 012。A0∩A11不是1吗是1对。A0∩A2宝石0在0宝石2在1或2。若宝石2在1宝石1在2排列 021若宝石2在2宝石1在1排列 012。共2。没错。A1∩A2宝石1在0或1宝石2在1或2。匹配1→02→1宝石0剩盒子2排列 201。1→12→2宝石0剩盒子0排列 012。 共2。没错。三个交集A0∩A1 已经推出宝石1只能放1A2 要求宝石2在1或2但1被占所以宝石2放2排列 012。1种。没错。那么 |A0∪A1∪A2| 244 -1-2-2 1 6。合法 6-60但枚举出 2 个合法。问题到底在哪功能性检查排列 120 是否属于 A1宝石1在2宝石1禁位 {0,1}不含2不属于 A1。是否属于 A2宝石2在0宝石2禁位 {1,2}不含0不属于 A2。是否属于 A0宝石0在1宝石0禁位 {0}不含1不属于 A0。所以 120 不属于任何坏事件应该在补集里。同理 210。补集应该有 2 个元素。可容斥算出的坏事件并集却是6。这意味着 A1 或 A2 计数时把某个不是坏事件的排列算进去了或者某个交集多算了。检查 A1 计数时列出的四个排列宝石1在0012、021宝石1在1102、201。它们是否都真的属于 A1当然A1 只要求宝石1禁位。但容斥并集还要看是否属于其他事件这没关系。所以 A14 没问题。A2 列出的宝石2在1201、210宝石2在2102、120。所以 A24。现在逐步看并集元素 A0 {012, 021} A1 {012, 021, 102, 201} A2 {102, 120, 201, 210} A0∪A1∪A2 {012, 021, 102, 201, 120, 210} 全部6个排列啊原来坏事件并集真的是全集补集是空集。那么为什么 120 和 210 合法因为它们确实不属于任何坏事件等一下排列 120宝石0在1宝石1在2宝石2在0。检查 A1宝石1在2但禁位是 {0,1}。不属于 A1。A2宝石2在0禁位{1,2}。不属于 A2。A0宝石0在1禁位{0}。不属于 A0。所以 120 确实不属于并集。但上面 A2 集合里我写了“宝石2在1201、210宝石2在2102、120”把 120 归入 A2 是因为宝石2在盒子2可是排列 120 是宝石0在1宝石1在2宝石2在0宝石2并不在2。是我把排列的表示写混了。用排列 012 表示“宝石0在0宝石1在1宝石2在2”。那么120 表示宝石0在1宝石1在2宝石2在0。宝石2在0不是1也不是2所以不属于 A2。210 表示宝石0在2宝石1在1宝石2在0。宝石2在0不属于 A2。所以 A2 计数里的列表错了。宝石2在1的排列是哪些宝石2固定在1剩下宝石0和1在盒子0和2任意排列 0210在0、1在2、2在1和 2010在2、1在0、2在1。宝石2在2的排列0120在0、1在1、2在2和 1020在1、1在0、2在2。所以 A2 {021, 201, 012, 102}大小4但元素和之前列的不一样。之前列 A2 时写“宝石2在1201、210”是错误的二元组写法210 是宝石0在2、宝石1在1、宝石2在0宝石2并不在1。我把排列的坐标理解错了。同样 A2 中“宝石2在2102、120”120 里宝石2也不在2。修正后 A0 {012, 021} A1 {012, 021, 102, 201} A2 {012, 102, 021, 201} A0∪A1∪A2 {012, 021, 102, 201}大小4。 补集 {120, 210}合法数2。这就对了。容斥公式本身没有问题是我手算时对于排列的表示和计数出现了纰漏。这个插曲正好说明这类题如果用容斥最后一定要拿暴力枚举或者对拍来验证手算中一个排列的位序搞错整个验算就废了。这也算是一条有价值的实战心得。回到表格修正后的容斥各项其实应该这样理解A02A14A24A0∩A11A0∩A22A1∩A22三交集1 并集244-1-2-216还是6。但并集元素明明只有4个。又矛盾了。等等A1∩A2 我算的是 2匹配“1→0且2→1”对应排列是什么宝石1在0宝石2在1宝石0剩盒子2排列 201。另一个“1→1且2→2”宝石1在1宝石2在2宝石0剩盒子0排列 012。所以 A1∩A2 {201, 012}。A0∩A1 {012}。A0∩A2宝石0在0宝石2在1或2若宝石2在1宝石1在2021若宝石2在2宝石1在1012。所以 A0∩A2{021, 012}。三重交集 {012}。容斥并集244 - (122) 1 6。但逐个并集列出是 {012,021,102,201}大小4。哪里多算了再看 A1 到底包含哪些排列。宝石1禁位 {0,1}A1 {012,021}宝石1在1∪ {102,201}宝石1在0。对。A2 {012,102}宝石2在2∪ {021,201}宝石2在1。对。A0{012,021}。并集A0∪A1∪A2 {012,021} ∪ {102,201} ∪ {102,012,021,201} {012,021,102,201}。确实4个。容斥计算却得6那肯定是某个交集大小错了导致减多了或加多了容斥条目的值单个和 10两两交集和 1225三重交集 1 10 - 5 1 6而真实并集4。所以两两交集或三重交集算错了。检查 A0∩A1A0{012,021}A1{012,021,102,201}交集{012,021}大小2不是1。我之前推导“宝石0在0宝石1在0或1若宝石1在0则冲突所以只能放1宝石2放2”忽略了宝石1还有另一个禁位 0但“宝石1在0”与“宝石0在0”确实冲突所以按这个逻辑 A0∩A1 确实只有 012 一种。但元素列举显示 021 也在交集里021 表示宝石0在0宝石1在2宝石2在1。宝石1在2不是禁位那 021 为什么属于 A1A1 定义是“宝石1踩雷”宝石1在2不属于禁位 {0,1}所以 021 根本不属于 A1。我之前列 A1{012,021,102,201} 时把 021 误收进来了。重新列 A1宝石1在1的排列012宝石0在0宝石1在1宝石2在2和 210宝石0在2宝石1在1宝石2在0。宝石1在0的排列1020在11在02在2和 2010在21在02在1。所以 A1{012,210,102,201}大小4。之前把 021 换进去是错的。A2宝石2在2的排列012 和 102宝石1在0。宝石2在1的排列021宝石0在0宝石1在2宝石2在1和 201宝石0在2宝石1在0宝石2在1。所以 A2{012,102,021,201}大小4。这个没变。A0{012,021}宝石0在0012、021。并集 {012,021,210,102,201}A1 有 210A2 有 021加上 {012,210,102,201} ∪ {012,102,021,201} ∪ {012,021} {012,021,210,102,201}大小5。但合法排列 210 难道不属于任何坏事件210 表示宝石0在2宝石1在1宝石2在0。宝石1在1而宝石1禁位 {0,1}宝石1确实踩雷了所以 210 属于 A1。于是 210 也是坏排列。那合法排列只剩 120 一个但枚举时我说 210 合法又错了。重新枚举全部 6 个排列按“宝石0宝石1宝石2”位置012宝石0在0踩雷宝石1在1踩雷因为禁位含1宝石2在2踩雷禁位含2。全坏。021宝石0在0踩雷宝石1在2合法宝石2在1踩雷。坏。102宝石0在1合法宝石1在0踩雷宝石2在2踩雷。坏。120宝石0在1合法宝石1在2合法宝石2在0合法。合法。201宝石0在2合法宝石1在0踩雷宝石2在1踩雷。坏。210宝石0在2合法宝石1在1踩雷宝石2在0合法。坏。合法方案只有 120 一个不是两个我之前忽略了宝石1的禁位也包括盒子1。所以正确答案是 1而不是2。用容斥重新算 A0 {012, 021} A1 {012, 210, 102, 201} A2 {012, 102, 021, 201} 两两交集 A0∩A1共同元素 {012}大小1。 A0∩A2共同元素 {012, 021}大小2。 A1∩A2共同元素 {012, 102, 201}大小3。 三重交集{012}大小1。 并集 244 - (123) 1 5。补集大小 6-51。合法方案 1 个与枚举一致。这下公式和枚举完全对上了。前面的失败经历再次说明一个问题这类题目里“禁位”与“排列表示”特别容易搞混宝石编号、盒子编号、排列中位置的含义必须在一开始就钉死否则手算验算会一错到底。最终这个例子的完整容斥表格应该是子集 S|S|交集计数容斥贡献∅066{0}12-2{1}14-4{2}14-4{0,1}211{0,2}222{1,2}233{0,1,2}31-1累加6 - 2 - 4 - 4 1 2 3 - 1 1。正确。这个例子放在这里很有价值它直观展示了“坏事件交集”怎么数也提醒读者容斥原理的每一项不是凭空想的必须逐个按排列元素核实。后续实现 DP 时这些细节会通过状态定义和位运算自动保证但在推导阶段仍然需要清醒。3. 状态压缩 DP把容斥的求和直接压进转移3.1 状态设计思路直接枚举所有宝石子集 S再对每个 S 计算 M(S)复杂度是外层 2^n内层还要做匹配计数很容易爆炸。对于 n ≤ 20 的规模更聪明的做法是设计一个 DP把容斥公式里的所有项边算边合并。观察容斥公式里最重要的一个事实最终每一项只关心 |S|也就是坏事件集合的大小因为 (n-|S|)! 只依赖这个数字。而 (-1)^{|S|} 也只依赖这个数字。真正麻烦的是 M(S)但 M(S) 的计数完全取决于“S 中哪些宝石踩了雷、各自占了哪个盒子”。如果我们按宝石编号顺序处理用一个二进制 mask 记录“当前已经被踩雷宝石占用的盒子集合”那么一颗宝石踩雷时它选择一个未占用的禁位盒子放进去如果它不踩雷就暂时不占盒子留到最后统一排列。这样定义状态 f[mask]处理完当前一批宝石后踩雷宝石占用盒子集合恰好为 mask 的方案数。注意这里没有记录“具体哪些宝石踩了雷”这是安全的因为宝石是按顺序处理的每一颗宝石只有一次机会决定是否踩雷状态转移路径已经隐含了已处理宝石的集合。初始状态 f[0]1表示没有任何宝石踩雷、也没有盒子被占。之后每处理一颗宝石 i它可以不踩雷f[mask] 原样保留它可以踩雷枚举一个自己的禁位盒子 b且 b 未被占用然后从 f[mask] 转移到 f[mask | (1b)]。处理完所有宝石后f[mask] 统计的就是所有情况下恰有 popcount(mask) 颗宝石踩雷、踩雷宝石占用的盒子集合为 mask 的方案总数。这个数本质上就是对所有满足 |S|popcount(mask) 的宝石子集 S 的 M(S) 求和。最后一步把容斥系数和自由排列因子加进去。对于每个 maskkpopcount(mask)它贡献的容斥项是(-1)^k · (n-k)! · f[mask]因为被踩雷宝石占用了 k 只盒子后剩余 n-k 只盒子和 n-k 颗自由宝石可以任意一一对应排列数是 (n-k)!。对所有 mask 求和就是完整答案。3.2 转移与滚动数组实现时最关键的一点是滚动数组。每次处理一颗宝石 i不能直接在 f 数组上做转移否则同一颗宝石可能被连续选中多次踩雷导致状态爆炸式增长且结果错误。正确写法是新建一个数组 g先把 f 整体复制过去这表示“宝石 i 不踩雷”的所有方案全部保留然后遍历 f 中的旧状态让宝石 i 从前置状态中踩雷一次把结果累加到 g 中。做完之后把 f 和 g 交换进入下一颗宝石。这里有个很微妙的逻辑为什么 g 的初始值必须等于 f而不是从空开始重新累加因为“这一颗宝石不踩雷”是一个合法选择它必须把所有旧方案完整传下去。如果你从全零数组开始转移等于默认每颗宝石必须踩雷结果会严重偏小。踩雷转移时还有一个细节宝石 i 的禁位集合里可能有多个盒子但同一颗宝石一次只能占一个盒子所以对于同一个旧状态 f[mask]枚举不同禁位 b 会产生不同的目标状态这些都要加进 g 中。枚举 b 时必须检查 (mask b) 1 是否为 0即 b 是否已经被之前的踩雷宝石占用。如果被占用这个转移不合法直接跳过。3.3 完整可运行的实现代码下面是这套思路的 C 实现。代码里统一使用 0-base 编号输入格式为第一行 n接下来 n 行每行先是一个整数 c表示该宝石禁位数量后面跟着 c 个盒子编号。#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorvectorint ban(n); for (int i 0; i n; i) { int c; cin c; ban[i].resize(c); for (int j 0; j c; j) { cin ban[i][j]; } } int total 1 n; // 阶乘自由宝石排列用 vectorlong long fact(n 1, 1); for (int i 1; i n; i) { fact[i] fact[i - 1] * i % MOD; } // 预处理每个 mask 的 popcount 和符号 vectorint pc(total, 0); vectorint neg(total, 0); for (int mask 1; mask total; mask) { pc[mask] pc[mask 1] (mask 1); } vectorlong long f(total, 0); f[0] 1; for (int i 0; i n; i) { vectorlong long g f; // 宝石 i 不踩雷 for (int mask 0; mask total; mask) { if (f[mask] 0) continue; for (int b : ban[i]) { if (mask (1 b)) continue; // 盒子已被踩雷宝石占用 int nmask mask | (1 b); g[nmask] (g[nmask] f[mask]) % MOD; } } f.swap(g); } long long ans 0; for (int mask 0; mask total; mask) { int k pc[mask]; long long term f[mask] * fact[n - k] % MOD; if (k 1) { ans (ans - term MOD) % MOD; } else { ans (ans term) % MOD; } } cout ans \n; return 0; }这个程序的核心循环只有两层外层宝石数 n中层状态数 2^n内层禁位数量。只要平均禁位数量不太大n20 的数据完全可以在常规时限内跑完。3.4 复杂度分析时间复杂度是 O(n · 2^n · avgBan)其中 avgBan 是所有宝石禁位集合大小的平均值。空间复杂度是 O(2^n)因为只需要保存两个长度 2^n 的数组。这个复杂度在 n20 左右是友好的。如果 n 到 22 甚至 252^n 就会膨胀到几百万甚至几千万内存和耗时都有压力。遇到更大的 n 时需要观察禁位集合的额外结构比如禁位集合是否有对称性、是否每个宝石禁位很少、是否可以把问题分解成若干个互不影响的连通块再用分块或者生成函数来处理。这是更进阶的优化方向。对比一下暴力枚举O(n! · n) 在 n10 时已经接近千万n12 就是几亿次操作基本不可用。而状态压缩 DP 把 2^n 级别的枚举和 n 阶的宝石处理结合起来让 n20 成为常规可解范围这是质的飞跃。4. 实操细节与常见坑4.1 最容易错的三个实现细节第一个坑是滚动数组的使用。我见过很多次有人写成这样先复制 gf然后在循环里用 g[mask] 作为转移源边算边把结果累加到 g[nmask]。因为 nmask 很可能大于 mask同一颗宝石 i 可能被连续用于多次踩雷转移导致方案数被无限放大。判断标准很简单一颗宝石要么踩雷要么不踩雷只能二选一如果新状态又回到自己身上继续扩展就说明它被重复使用了。第二个坑是禁位集合里可能有重复的盒子编号。数据如果保证所有禁位互不相同这个问题不会出现但如果输入不规范同一颗宝石的禁位列表里出现两次盒子 b那么代码里会把同一个转移执行两次答案虚高。稳妥做法是在读入后对每颗宝石的禁位列表做一次 sort 和 unique。第三个坑是容斥系数和阶乘因子的顺序。如果在最后累加时忘记乘 fact[n-k]或者把 (-1)^k 的符号搞反答案会完全错误。建议把容斥公式先写在代码注释里保证最后一段代码和公式一一对应而不是靠记忆写。4.2 常见错误速查表下面这张表整理了我在实际写题和帮人排查时遇到过的一些典型错误可以直接当检查清单用。错误类型现象原因修正办法滚动数组写错答案异常大同一颗宝石被重复选为踩雷转移源必须用旧数组 f忽略重复禁位答案偏大禁位列表有重复盒子读入后 sort unique未检查盒子占用答案偏大踩雷宝石互相抢同一盒子转移前判断 mask (1b)符号处理错误答案偏小或为负容斥系数符号反了检查最后累加中的 if (k 1)忘记空集贡献少了 n!循环从 mask1 开始mask 从 0 开始遍历阶乘溢出答案错误中间乘法超出 long long每次相乘取模取模后减法为负答案负数减法后未加 MOD用 (ans - term MOD) % MOD这里特别要强调一下空集贡献。很多人在实现容斥时习惯先累加所有坏事件最后再让 ans fact[n] - bad这没有问题。但如果写成循环从 mask1 开始累加项最后忘了手动把 fact[n] 加进来答案就会少掉最大的那一项。我的建议就是代码里 mask 从 0 开始遍历让空集作为普通一项目然参与求和不容易漏。4.3 对拍与验证建议对于这种计数题写完正解之后最好再写一个暴力验证。暴力逻辑很简单枚全排列检查每个宝石是否落在禁位里统计合法排列数量。n 不超过 8 或 9 时暴力结果可以秒出。我个人的习惯是写一个对拍脚本随机生成 n 在 5 到 8 之间的数据每个宝石随机分配 0 到 3 个禁位跑几百组把暴力结果和 DP 结果逐一比对。只要有一组不一致就缩小 n手动模拟那组数据。通常能快速定位到是符号问题、滚动数组问题还是 mask 位运算优先级问题。还有一个低成本验证技巧跑 n 较小且所有 ban[i] 为空的特例。这种情况下答案必须是 n!。再跑所有 ban[i] 为 {0,1,...,n-1} 的特例每颗宝石哪里都不能去答案必须是 0。这两个极端用例能挡住绝大多数低级实现错误。5. 扩展换条件时这套思路还能怎么用5.1 盒子数多于宝石数如果盒子数 m 大于宝石数 n且规则仍然是每只盒子最多一颗宝石那么 DP 状态里的 mask 要开到 m 位。最后容斥项里的自由排列因子不再是 (n-k)!而是从剩余 m-k 只盒子里选出 n-k 只并分配给 n-k 颗自由宝石的方案数P(m-k, n-k) (m-k)! / (m-n)!代码上只需把 fact[n-k] 换成一个预处理好的下降阶乘数组或者用一个函数计算 P(a,b) 即可。DP 转移完全不用改因为踩雷宝石占用盒子的逻辑和 nm 时一模一样。这个扩展在实际题目中很常见比如盒子比宝石多意味着有若干盒子会空着但空盒不影响禁位冲突的计数。容斥公式依然成立因为坏事件的定义没有变。5.2 每个盒子允许放多颗宝石如果规则变成每个盒子可以装任意多颗宝石问题反而变简单了因为“踩雷宝石互相抢盒子”的约束消失了。容斥项中的 M(S) 不再是匹配方案数而是∏_{i∈S} |ban[i]|因为 S 中的每颗宝石可以独立地从自己的禁位集合里选一个盒子无需考虑其他宝石是否选了同一个盒子。这种情形下不需要状态压缩 DP直接枚举宝石子集累加即可复杂度 O(2^n · 总禁位数)。这也是一个很好的对比正是一对一排列约束造成了盒子冲突才让状态压缩 DP 成为必需品。如果题目去掉“每盒一颗”的限制很多复杂度问题就消失了但模型也不再是经典的“装箱排列”问题。5.3 禁位集合的结构特殊化如果禁位集合有特殊的结构可以避开 2^n 的状态。最典型的就是错排每个宝石只有一个禁位且禁位互不相同此时 M(S)1公式化简为 n! Σ (-1)^k / k!O(n) 甚至 O(1) 都能算。另一种常见结构是禁位集合形成若干个连通块。比如把宝石和盒子看作二分图禁位关系是边如果图被分割成多个互不相连的连通块那么每个连通块可以独立做 DP最后用组合数把各块方案数合起来。这个优化能把 n30 甚至更大的问题压到可解范围因为 2^30 是十亿级别而拆成两个 2^15 分别 DP 后复杂度大幅下降。还有一种情况是宝石之间存在强约束比如若干颗宝石的禁位集合完全一样那么这些宝石会同构可以先做等价类划分再来 DP。这类优化需要具体问题具体分析不是通用套路但值得在遇到大范围数据时多想一想。5.4 与错排、排列数公式的关系整个容斥 DP 的框架本质上是在处理带禁位的排列计数。错排只是其中禁位集合为 {i} 的特例。当禁位集合变成任意图时这个框架依然成立只是 M(S) 的计算从平凡变成了需要 DP。如果从更高的视角看这个问题的答案是“禁位二分图的补图的完美匹配数”。容斥原理相当于用“哪些匹配边落在禁位图内”作为坏事件对坏边集合做展开。状态压缩 DP 是在逐颗宝石地累积这些坏边选择方案。理解了这层关系再遇到类似问题时就能快速判断只要坏事件可以被定义成“某元素落在了禁止目标上”并且其余元素的排列数可以独立计算容斥框架就适用。6. 写在最后的一点体会这套解法我在实战中大概写过很多遍最深的体会是容斥原理不是只能用来推公式它完全可以作为算法设计的骨架。很多人把容斥理解成手工数学题的工具一旦要写代码就只想着怎么把合法状态塞进 DP但实际上把容斥项拆进状态转移往往是更省事的路。关键在于分清哪些事是“强制发生的坏事件”哪些事是“自由发生的背景”“强制”的部分用状态记录冲突“自由”的部分用阶乘批量计数。最后再分享一个调试小技巧如果 n 不大但答案总是错先不要急着盯代码自己在纸上跑一个 n3 的全枚举把坏事件并集元素逐个列出来再用容斥公式对照。很多时候问题不是出在代码而是出在你对事件定义的理解上。比如我这次在构建示例时一度因为排列表示和禁位含义没对齐算出来的结果怎么都对不上最后逐个排列排查才找到问题。把定义理清楚再回过来看代码很多 bug 会自己现形。
