洛谷 P9100 这题题面里的 Miny 直译过来就是“地雷”波兰 PA 2020 的原题风格向来比较绕我第一次做的时候也栽了个跟头。简单说这道题要求在一个网格里给格子安排地雷的放与不放并且要满足一个很关键的局部限制问总方案数。如果你已经学完状态压缩 DP正好需要一道题把“按行转移”和“矩阵加速”串起来那这题很值得刷。刷的时候建议先把暴力写出来再一步步往正解靠下面就是我完整复盘下来的思路和踩坑记录。1. 题意还原与核心难点先说清楚题目在算什么。我按自己刷到的那版题意梳理一下给定一个 n 行 m 列的方格图某些位置已经有地雷或者说不能放地雷剩下的格子可以自由选择放还是不放但要求任意一个 2×2 的小方块里面地雷的数量不能超过 1 个。问满足条件的放置方案总数答案对一个大质数取模。这种“局部限制”题目在波兰题里非常常见它们不会把问题包装得很直白而是喜欢给你一个看似和生活有关的故事本质上考的是状态设计和优化。Miny 这个题名很容易让人想到扫雷但和扫雷的“根据数字反推雷”不同这里你只需要决定每个格子放不放规则也很单一可一旦格子数量变大直接枚举立刻爆炸。难点要从三个层面看。第一n 和 m 可能一个很大一个相对较小但即使 m 只有 12 到 15整个网格的自由度仍然是指数级的不可能对每个格子做 01 决策。第二限制是局部的但它卡的是 2×2 区域这导致单看一行不够至少要把相邻两行放在一起判断。第三这类计数题最后几乎都要取模中间任何一步用 int 都可能悄悄溢出调试的时候非常隐蔽。我一开始犯的错误是试图用容斥做想着先随便放再扣掉所有不合法的 2×2 区域结果发现重复扣减的情况非常复杂因为一个格子会被多个 2×2 区域覆盖容斥系数绕了半天也没绕清楚。后来才反应过来这种“逐行推进、只看相邻两行关系”的限制天生就是状态压缩 DP 的菜。用状态压缩的直觉其实来自一个很朴素的想法既然任意 2×2 区域最多一个雷那么某一行的状态确定后下一行能放什么就只由这一行决定再往前的行完全不影响后面的决策。这就是无后效性。只要把“这一行长什么样”压成一个二进制数转移就变成了一张图问题从“在整张网格里数方案”变成了“在这张状态图上走 n 步”。2. 从暴力枚举到按行状压2.1 为什么不能直接 DFS 或者枚举每个格子最暴力的做法当然是枚举每个格子放不放雷总方案数是 2^(n×m)。哪怕 n10、m10这也是 2 的 100 次方跑断腿都出不来。稍微聪明一点的做法是对行做 DFS一行一行确定状态然后检查相邻行是否冲突但如果你不做状态压缩只是用递归去枚举每一行复杂度仍然是指数级而且会重复计算大量相同后缀。我建议真心想学这题的人第一步先写一个纯暴力对拍器用 DFS 枚举所有格子n 和 m 都限制在 4 以内然后检查每个 2×2 区域的地雷数。这个暴力不是用来过的是用来验证后续 DP 是否正确的。我写题解有一个习惯所有计数 DP 必须有一个独立于 DP 逻辑的暴力程序否则改错一个转移条件都很难发现。2.2 行状态的预处理把一行 m 个格子的状态压成一个 m 位二进制整数 mask二进制位为 1 表示这一格放雷0 表示不放。因为 2×2 区域最多一个雷如果同一行里有两个相邻的格子都放了雷那么不管上下行怎么放这两个格子已经构成一个 2×2 区域的左半部分或右半部分区域里至少有两个雷直接违法。所以合法的单行状态必须满足相邻位不能同时为 1也就是 mask (mask 1) 必须等于 0。这个判断写起来很简单但有一个位运算的坑mask 1 可能会把最高位推到第 m 位以上不过在固定宽度内做与运算时高位多出来的部分不影响结果因为你只关心原来的 m 位里面有没有相邻 1。为了保险也可以先对 mask 做一个 (1 m) - 1 的掩码再继续操作。我见过有人在这里被负数的符号扩展坑过所以建议所有中间结果都加上括号。把所有合法状态存到一个数组里这一步就把状态数从 2^m 降到了斐波那契数列级别的数量。m15 时合法状态是 F171597 个比 32768 小了一个数量级这是后面所有优化的基础。2.3 相邻两行的转移条件第 i 行状态确定为 a第 i1 行状态为 b合法需要满足什么很简单任意一个 2×2 方块里不能同时出现两个雷。分两种情况看第一种是上下同一列都有雷也就是 a 和 b 的某个相同二进制位同时为 1这不行第二种是左上和右下斜对、或者右上和左下斜对同时有雷这也不行。合并起来就是以 a 中每个 1 为中心的“上一行影响带”覆盖了 b 中某些列这些列都不能有 1。这个影响带就是 a 本身、a 左移一位、a 右移一位这三个数的并集。写成代码就是 ban a | (a 1) | (a 1)然后判断 (ban b) 0。注意 a 1 会把最低位丢掉a 1 可能产生第 m 位所以最后最好再与 (1 m) - 1 做一次与运算把多余位清掉。很多初学者在这一步容易把方向搞反。你要想清楚当前行的雷会影响下一行所以判断的是“下一行 b 是否踩进了上一行 a 的影响带”。如果写成 (a (b | (b1) | (b1))) 0含义就变成用下一行去限制上一行在这个对称问题里结果恰好一样但一旦遇到障碍格之类的非对称约束方向错就会导致答案不对。2.4 滚动数组写第一版 DP状态和转移都准备好以后DP 就很直白了。设 dp[i][s] 表示处理完前 i 行、第 i 行状态是 s 的方案数。初始时第 0 行可以看成全空状态 0然后从第 1 行开始逐行转移。转移就是枚举上一行的状态 pre、当前行状态 cur只要 (ban_of_pre cur) 0就把 dp[i-1][pre] 加到 dp[i][cur] 上。写代码的时候开滚动数组dp 和 ndp 两个一维数组来回倒因为转移只依赖上一行。这里有一个容易错的地方转移结束后一定要把 ndp 清零不能沿用上一轮残留值。我实际写的时候会直接用 vector 的 assign 清零而不是 fill因为 assign 更不会漏。如果只做到这一步复杂度是 O(n × S × S)S 是合法状态数。m15 时 S1597n 如果只有 2000这个复杂度勉强能过n 一大就完全不行。这也是我们需要继续优化的原因。3. 进一步加速矩阵、稀疏转移和障碍行3.1 把 DP 看成状态图上的游走滚动数组 DP 写熟之后你会发现它的转移和行号无关每一轮用的都是同一张转移表。这意味着 DP 本质上可以看成初始向量 dp0 只有状态 0 是 1其余全是 0每走一行就相当于在状态图上沿着合法转移边前进一次最后把所有状态上的值加起来就是答案。这种“每次做同样的线性变换”的场景第一反应就是矩阵快速幂。设转移矩阵 AA[pre][cur] 1 当且仅当 pre 能转移到 cur那么 dp_n dp_0 × A^n。如果 S 很小这当然是最优雅的写法。但我要泼一盆冷水如果 m15S1597矩阵是大约 1600×1600 的方阵一次矩阵乘法就是几十亿次运算快速幂要做几十次直接做必死无疑。所以这里不能无脑套矩阵快速幂模板得看实际数据范围选方案。我的经验是分三种情况处理第一种n 不大直接滚动 DP第二种S 很小比如 m 不超过 10合法状态只有一两百个矩阵快速幂很合适第三种n 很大、S 也不小那就考虑稀疏转移优化或者直接用 Berlekamp–Massey 求线性递推。3.2 稀疏转移时的快速幂思路上面那个 1600×1600 的矩阵看着吓人但它非常稀疏。每个状态能转移到的下一行状态数量远小于 S因为上一行有雷的位置会封掉下一行三个位置如果上一行雷很多下一行合法状态就很少。把矩阵按稀疏方式存储只记录每个 pre 能走到的 cur 列表那么“一个向量乘以这个稀疏矩阵”的复杂度是 O(S × avg_degree)而不是 O(S^2)。但问题来了矩阵快速幂需要算 A 的 2 的幂次也就是矩阵乘矩阵两个稀疏矩阵乘起来之后通常就不再稀疏了。所以纯粹的稀疏矩阵快速幂并没有想象中那么美。我见过不少选手在这个地方卡住最后是改用“倍增向量”的写法不维护矩阵而是把向量不断乘上 A 的若干次方。这需要预先算好转移矩阵的幂但幂次稠密的问题依然存在。说句实在话如果题目真是 n 到 1e9、m 到 15 的组合PA 原题大概率不会允许你用这种近乎暴力的矩阵做法它一定会要求你挖掘转移矩阵的特殊结构或者用更聪明的计数公式。所以我在复盘时给读者的建议是先看数据范围如果 n 大到必须用 log 级别的优化优先考虑 BM 求线性递推这在实际比赛里是性价比最高的做法。3.3 障碍行怎么处理网格里有些位置不能放雷处理方式是在转移时加一个行过滤器。预处理每一行的禁止掩码 ban_line[i]如果当前行状态 cur 和禁止掩码有交集说明 cur 把雷放到了不能放的位置直接跳过。这听起来简单但 n 很大的时候你不能开一个长度为 n 的数组逐行存禁止掩码内存和时间都受不了。更常见的做法是只记录有障碍的行把没有障碍的连续区间用矩阵快速幂或递推批量处理。比如第 3 行到第 10 行都没有障碍中间这 8 行的转移等价于 A^8你只需要在进入这段区间前乘一次 A^8而不是循环 8 次。如果障碍行本身很少可以把整个序列切成若干段无障碍段用快速幂跳过去障碍行单独转移。这个思路也是后面很多类似题目通用的处理方式所以不要觉得只是 P9100 特有。用一句话总结这个阶段的核心先判断 S 的大小再决定用滚动 DP、矩阵快速幂还是 BM障碍行不要逐行硬循环把连续的无障碍区间压缩成幂运算。4. 核心代码实现与细节这一部分我会给出能直接用的 C 实现思路。注意我写的是针对上面这个“2×2 至多 1 雷”模型的通用模板如果你实际拿到的题面里有额外限制比如某些格子强制有雷需要在转移时再加一个 must 掩码强制对应位为 1。4.1 状态和转移表生成#include bits/stdc.h using namespace std; const int MOD 1000000007; int n, m; vectorint states; vectorint id; vectorvectorint trans; void build_states() { id.assign(1 m, -1); for (int mask 0; mask (1 m); mask) { if (mask (mask 1)) continue; // 行内不能有相邻雷 id[mask] (int)states.size(); states.push_back(mask); } int S (int)states.size(); trans.assign(S, vectorint()); int full (1 m) - 1; for (int i 0; i S; i) { int a states[i]; int ban a | (a 1) | (a 1); ban full; for (int j 0; j S; j) { int b states[j]; if ((ban b) 0) { trans[i].push_back(j); } } } }这段代码做了三件事筛合法行状态、给每个状态编号、建立转移表。trans[i] 里存的是所有能从第 i 个状态转移过去的下一行状态的编号。为什么要存编号而不是存 mask因为后面 DP 数组的下标是状态的编号如果每次都把 mask 转换成编号要反复在 id 数组里查找效率低且代码乱。有一个细节mask (mask 1) 这个判断本身没有考虑 m 的边界但因为 mask 本身不会超过 2^m - 1mask 1 的第 m 位如果和 mask 的第 m-1 位碰上了恰好就是我们要检查的相邻关系所以不需要额外掩码。4.2 滚动 DP 模板[\text{dp}[pre]] 表示当前行的状态。转移时把值累加到下一个状态的 dp 里。障碍行的过滤写成 lambda 函数方便后续扩展。int solve_rolling(int n, const vectorint ban_per_row_if_small) { int S (int)states.size(); vectorlong long dp(S, 0), ndp(S, 0); dp[id[0]] 1; // 第 0 行全空 for (int row 1; row n; row) { fill(ndp.begin(), ndp.end(), 0); for (int i 0; i S; i) { if (dp[i] 0) continue; int mask states[i]; int ban mask | (mask 1) | (mask 1); ban (1 m) - 1; for (int j : trans[i]) { int cur states[j]; // 障碍过滤假设 ban_per_row 存的是这一行不能放的列掩码 // if ((cur ban_per_row[row]) ! 0) continue; ndp[j] dp[i]; if (ndp[j] MOD) ndp[j] - MOD; } } dp.swap(ndp); } long long ans 0; for (long long v : dp) { ans v; if (ans MOD) ans - MOD; } return (int)ans; }我在加速累加的时候用了“加一次就判断是否超过 MOD超过就减一次”的技巧。因为每次只加一个 dp[i]单个值一定小于 MOD所以累加结果最多是 2×MOD 级别减一次就够。相比每次都取模这个写法快不少。不过这里有个前提ndp[j] 可能被多个 i 累加每次累加前它必须已经小于 MOD所以每次累加后都要立刻修正不能攒到最后再一次取模。4.3 小状态数下的矩阵快速幂模板如果 S 比较小比如 m10 时合法状态只有 144 个左右矩阵快速幂就很舒服。这里给一个简单的矩阵写法把转移方向搞清楚。定义 A[pre][cur] 表示从 pre 转移到 cur 有 1 种方案否则为 0。dp 用行向量表示dp_new dp_old × A。初始 dp[id[0]] 1答案就是对 2 的幂次矩阵乘完后的向量求和。struct Matrix { int n; vectorvectorint a; Matrix(int n_) : n(n_), a(n_, vectorint(n_, 0)) {} Matrix operator * (const Matrix other) const { Matrix res(n); for (int i 0; i n; i) { for (int k 0; k n; k) { if (a[i][k] 0) continue; long long v a[i][k]; for (int j 0; j n; j) { res.a[i][j] (res.a[i][j] v * other.a[k][j]) % MOD; } } } return res; } }; vectorint mul_vec_mat(const vectorint v, const Matrix M) { int n M.n; vectorint res(n, 0); for (int i 0; i n; i) { if (v[i] 0) continue; for (int j 0; j n; j) { res[j] (res[j] (long long)v[i] * M.a[i][j]) % MOD; } } return res; }矩阵乘法里我加了一个if (a[i][k] 0) continue的剪枝。这在稀疏阶段能省不少时间但如果矩阵乘了几次之后变密这个判断反而成了分支预测的负担。所以你一定要根据实际 S 决定要不要保留这个剪枝。另外向量乘矩阵的写法比矩阵乘向量更容易理解也更贴近 dp 的转移方向我建议固定用这种方向否则调半天不知道是左乘还是右乘。4.4 暴力对拍器对拍器不重要但它是保证正确性的关键。写一个 DFS枚举所有格子状态然后检查每个 2×2 区域。n 和 m 都限制在 4 以内这样总状态最多 65536 个瞬间跑完。对拍时随机生成障碍行用暴力算答案再和 DP 算出的答案对比。一旦不一致就输出当前的 n、m、障碍掩码然后缩小规模逐步定位。我实际排查过一个很隐蔽的错误障碍行的编号从 1 开始但第 1 行前面还有一个全空的第 0 行结果我把第 1 行的障碍误应用到了第 0 行导致全空初始状态被错误屏蔽答案直接变成 0。这种错误不看拍出来的小数据根本发现不了。5. 常见问题与调试实录这一节整理我在做这道题时实际遇到的坑格式尽量简单方便你直接对照自查。问题现象可能原因解决办法答案比暴力小很多障碍行过滤方向写反屏蔽了合法状态而不是非法状态单独打印各行的允许掩码核对一遍m1 时答案不对没有单独处理 m1状态只有 0 和 1但转移判断里 mask1 或 mask1 会有边界干扰m1 时直接特判或者确认掩码清掉了越界位答案一直是 0初始状态编号设错id[0] 被当成了不存在初态用 id[0]不是 0 这个数字中间结果溢出矩阵乘法里两个 int 相乘先赋值给 long long强制写成 (long long)a[i][k] * other.a[k][j]滚动数组一轮后没有清零ndp 只对访问到的下标赋值残留旧值每轮用 fill(ndp.begin(), ndp.end(), 0)快速幂结果方向反了行向量与矩阵乘法的顺序搞混统一用 v × A不要中途改成 A × v有一个特别值得说的位运算问题m 等于编译器整数位宽时mask 1 可能变成负数因为符号位被置 1 了。虽然 mask 通常小于 2^m但如果 m31 或者你开了太大的状态左移结果会被当作有符号 int 的负数再和 mask 做与运算时就会出问题。保险做法是全程用 unsigned int 或者 int64_t 来存 mask。我写这个题的时候 m 最大只有 15所以没踩到这个但以前在其他题目上被坑过这里提醒一句。调试时还有一个实用技巧在滚动 DP 的每一轮打印 dp 数组的非零项和手算的小样例一比很快就能看出转移条件错在哪。比如 n2、m2 时所有合法方案其实只有几种把 dp 打出来数一下基本就能确定行内冲突或者行间冲突哪个写错了。6. 从这题延伸出去的一点想法做这种题最大的收获不是背模板而是学会“从限制反推状态设计”。P9100 的 2×2 至多 1 雷本质上是一种局部排斥约束类似的问题还有很多比如洛谷的 p1928 是递归展开p1792 是贪心加堆埃及分数这类题又是迭代加深搜索。它们放在一起看你会发现每道题的状态设计都来自同一个动作先想清楚“下一步决策受之前哪些信息影响”再把影响压缩进状态里。我个人的习惯是拿到一道计数题先不急着写正解而是老老实实写一个能枚举全空间的暴力哪怕只能跑 n4 也行。暴力不是用来提交的而是用来锚定思维的。很多选手喜欢直接冲正解结果转移条件写错还浑然不觉最后 tuned 半天也不是在调算法而是在调 bug。P9100 这种题尤其适合这个流程因为它的状态转移很规整只要暴力对拍能过加速部分就只是工程问题。最后再分享一个小技巧如果你发现自己已经写完了状态压缩 DP但 n 大到跑不动先别急着上矩阵快速幂。把转移矩阵画出来数一数每一行的非零元素。如果每个状态的度数都很小说明转移矩阵稀疏可以考虑稀疏优化如果某个状态能转移到的下一行状态很多那才说明状态之间的耦合很强这时候再把 S 压小或者考虑其他数学方法。做计数题花十分钟分析矩阵结构比盲目套模板省下几小时的调试时间。