AcWing 291 的《蒙德里安的梦想》是状态压缩 dp 里绕不开的一道入门题。题面很文艺把 NM 的棋盘分割成若干个 12 的长方形问有多少种方案。但真正动手做的时候很多人会被“状态压缩”这四个字吓住觉得又要位运算又要滚动数组门槛不低。我当年第一次做这道题也曾在状态定义上绕了整整一个晚上后来把“横着伸出去的格子”这个视角想透之后再看同类状压题基本都是一路平推。这篇文章不打算讲虚的直接带你把模型、代码、易错点全部过一遍。无论你是刚学 DP 的新手还是刷题想查漏补缺的老手这篇应该都值得花十分钟读完。1. 题目到底在求什么先别急着看状态压缩1.1 一个拿 1x2 小长方形铺满棋盘的问题题目给一个 N 行 M 列的棋盘要求用若干个 1*2 的小长方形把它完全覆盖。小长方形可以横着放也可以竖着放不能重叠不能漏格子问一共有多少种不同的摆放方案。比如 24 的棋盘一共只有 5 种方案13 的棋盘方案数是 0因为 3 个格子不可能被 1*2 的方块刚好铺满。题目会输入很多组 N 和 M直到读入 0 0 结束。我当年刚看到这题的时候第一反应是这不就是组合数学里的多米诺铺棋盘吗如果是 2*M答案是斐波那契数列有现成公式。但 N 和 M 一大情况立刻变得非常复杂。再加上题目名又是“蒙德里安的梦想”这种艺术气息浓厚的名字很容易让人误以为要画格子找规律。实际上这道题真正的考点是状态压缩 DP而且 N、M 的范围只到 11这个数据范围本身就是最重要的提示。1.2 为什么朴素搜索会炸如果不假思索直接 DFS会怎么做从某个格子开始要么不放、要么横放、要么竖放然后递归处理剩余棋盘。听起来简单实际跑起来非常可怕。因为棋盘最大 1111放一个方块只覆盖两个格子全局搜索树的深度大约是格子数的一半每次还有分叉搜索空间是指数级的。就算加上对称性剪枝、可行性剪枝也很难处理 411 这种比较“长窄”的棋盘。换句话说这不是一道能靠暴力枚举摆法解决的问题。我们需要一种方式把“棋盘全局状态”压缩成“某一列的局部状态”然后通过列与列之间的转移来统计方案。这就是状态压缩 DP 出现的原因。1.3 旋转棋盘与数据范围的信号N 和 M 都小于等于 11意味着 2^11 2048这个数字很舒服。状态压缩 DP 的复杂度基本都跟 2^N 有关N 小是前提。这里还有一个很容易被忽略的优化如果 N M可以把棋盘旋转 90 度也就是 swap(N, M)。因为 1*2 小长方形本身可以横放也可以竖放旋转之后每种覆盖方案还是一一对应的方案数不变。但交换之后我们通常让较小的那个数作为“状态位数”较大的那个作为“阶段数”这样总复杂度更低。题目数据范围小不交换也能过但这个习惯值得养成后面遇到 n 很小 m 很大的变体题时就是保命技巧。2. 核心建模用二进制表示“伸出去的格子”2.1 状态定义上一列伸到当前列的状态状态压缩 DP 的关键在于到底压缩什么这个问题里我们按列从左往右扫描。一个横着放的 1*2 小长方形会同时占第 i 列和第 i1 列的各一个格子。如果我们在处理第 i 列时决定放一个横块那么它就会“伸到”第 i1 列去。这个“伸出去”的信息必须记录在状态里否则处理下一列时不知道哪些格子已经被占用了。于是就有了这道题最经典的状态定义f[j]表示上一列伸到当前列的状态是 j 的方案数。这里 j 是一个 N 位二进制数第 r 位为 1表示第 r 行有一个横块从上一列伸到了当前列占据当前列的这一个格子。举个例子如果 N 5j 0b00110表示第 1 行和第 2 行从低位编号各有一个横块从左边伸到了当前列。为什么要定义成“伸出去”而不是定义成“当前列已经覆盖了哪些格子”因为当前列内部的放置情况其实是可以由剩余空格推导出来的。一旦知道了哪些格子被横块占掉了剩下连续的空格只能由竖块填满而竖块是否合法只跟空格段长度有关不需要额外记录更细的信息。所以一个 N 位二进制数就足以描述当前列对下一列产生的影响这已经是最小且完备的信息。2.2 合法转移的两个条件不重叠、空格成双现在假设在处理第 i 列时从第 i-1 列伸过来的状态是 j。我们要选择一个新的状态 k表示第 i 列有哪些格子会伸到第 i1 列去。这个选择必须满足两个条件。第一个条件非常直观(j k) 0。因为同一个格子不可能同时被左边伸来的横块占住又向右边伸出一个横块。如果 j 和 k 在某一位上都是 1说明这个格子上叠了两个方块方案非法。第二个条件稍微隐蔽一点valid[j | k]必须为真。这里的j | k表示当前列所有被横块覆盖的格子集合。去掉这些被横块覆盖的格子后剩下的空格必须全部由竖块填充。一个竖块占连续的两格所以连续空格的每一段长度都必须是偶数。可以这样理解横块就像钉子把当前列切成好几段空格每一段空格都必须能被竖块正好填满所以每一段的长度都必须是偶数。如果某一段空格的个数是奇数最后一定会留下一个格子塞不进去方案就不可行。2.3 预处理 valid 数组判断连续 0 的个数是不是偶数判断一个状态 s 的每一段连续空格长度是否都是偶数可以提前预处理。这个处理不依赖列号输入一组 N 之后算一次就行。一个状态的二进制表示中1 表示该位置有横块覆盖0 表示空格。我们只需要扫描这个二进制数记录当前连续 0 的个数遇到 1 就检查之前那段 0 的个数是不是偶数最后再检查末尾一段 0。下面这个函数或者预处理片段是核心int total 1 n; vectorbool valid(total, false); for (int s 0; s total; s) { int cnt 0; bool ok true; for (int i 0; i n; i) { if ((s i) 1) { if (cnt 1) { ok false; break; } cnt 0; } else { cnt; } } if (cnt 1) ok false; valid[s] ok; }这里有个特别容易出错的地方一定要在循环结束后再检查一次cnt。因为如果末尾是一串 0循环里没有遇到 1 来触发检查最后的连续空格长度就会被漏掉。举个例子N 3 时状态 0 表示当前列没有横块覆盖。整列 3 个格子全是空格但 3 是奇数不可能用竖块把 3 行填满所以valid[0]是 false。这个细节很关键很多初学者看到状态 0 就条件反射觉得一定合法其实不一定。3. 完整代码与逐段注释不搞玄学直接能 AC3.1 预处理转移表直接写三层循环枚举 j 和 k 也能过但既然 valid 判断和转移条件只跟当前 N 有关完全可以把每个状态 j 能转移到的所有合法 k 预先存下来DP 时只需要查表累加。这样代码更清晰速度也更快。对于状态 j另一个状态 k 能合法转移的条件是(j k) 0valid[j | k]为 true把所有满足条件的 k 存进trans[j]DP 时直接枚举trans[j]里的元素。3.2 DP 转移滚动数组写法完整 C 代码如下#include bits/stdc.h using namespace std; int main() { int n, m; while (cin n m, n || m) { // 让较小的数作为状态位数较大的数作为阶段数 if (n m) swap(n, m); int total 1 n; // 1. 预处理每个列状态是否合法 vectorbool valid(total, false); for (int s 0; s total; s) { int cnt 0; bool ok true; for (int i 0; i n; i) { if ((s i) 1) { if (cnt 1) { ok false; break; } cnt 0; } else { cnt; } } if (cnt 1) ok false; valid[s] ok; } // 2. 预处理合法转移表 vectorvectorint trans(total); for (int j 0; j total; j) { for (int k 0; k total; k) { if ((j k) 0 valid[j | k]) { trans[j].push_back(k); } } } // 3. DP vectorlong long f(total, 0), nxt(total, 0); f[0] 1; // 第 0 列没有前一列伸来的状态 for (int i 1; i m; i) { fill(nxt.begin(), nxt.end(), 0); for (int j 0; j total; j) { if (f[j] 0) continue; for (int k : trans[j]) { nxt[k] f[j]; } } f.swap(nxt); } cout f[0] \n; } return 0; }3.3 转移过程的含义这里我再仔细解释一下滚动数组里的 f 和 nxt 分别代表什么避免看代码的时候脑袋晕。进入第 i 轮循环前f[j]表示前 i-1 列已经全部铺好并且从第 i-1 列伸到第 i 列的状态是 j 的方案数。初始时第 0 列不存在也没有任何一列伸到第 1 列所以f[0] 1。循环内对于当前状态 j枚举一个状态 k 作为“第 i 列伸到第 i1 列”的状态。如果 j 和 k 满足合法转移条件那么就把f[j]累加到nxt[k]中。一轮循环结束后nxt[k]的含义自然就变成了前 i 列已经全部铺好并且从第 i 列伸到第 i1 列的状态是 k 的方案数。所以经过 m 轮循环也就是处理完了所有 m 列答案就是f[0]。f[0]表示第 m 列没有任何一个横块伸到第 m1 列也就是整个棋盘刚好被完全铺满。3.4 测试样例和复杂度用上面代码跑几组数据可以得到NM输出12113022223324521114441151205如果你熟悉斐波那契会发现 2M 的情况输出正好是斐波那契数列22 是 223 是 324 是 52*11 是 144。这说明整个状态压缩模型在特殊情况下也能退化成我们熟悉的结论能够作为自测的一个验证手段。复杂度方面valid 预处理是 O(n * 2^n)转移表预处理是 O(4^n)DP 过程大约是 O(m * 转移边数)最坏大概是 O(m * 4^n)。当 n 11 时4^11 约 400 万再乘 m 11也就四千多万次加法C 轻松跑完。如果不用转移表直接在循环里判断也差不多是这个量级仍然能过。4. 我在这道题上踩过的坑位运算优先级、状态含义错位4.1j k 0为什么不加括号会出事这是状态压缩题里最经典的 C 坑没有之一。if (j k 0) { ... }这段代码看起来像在判断j k是否等于 0但 C 的运算优先级里的优先级高于。所以它会先算k 0得到一个布尔值 0 或 1再跟 j 做按位与。结果完全不是你以为的意思。正确写法是if ((j k) 0) { ... }这种 bug 非常难查因为程序不会崩溃只会给出一个可疑的大答案。我第一次写的时候就被坑过一次后来我给自己定了个规矩位运算和比较运算符混在一起时一律加括号不要依赖记忆。4.2 只看valid[j]和valid[k]却漏了valid[j | k]有段时间我以为只需要分别判断上一列伸过来的状态 j 合法以及当前列伸出去的状态 k 合法然后只要不重叠就行。这个想法是错的。因为当前列真正被横块覆盖的集合不是 j 也不是 k而是j | k。两个状态单独合法合并之后不一定合法。我举个具体的反例N 6 的时候j 0b001100连续空格段是 2 和 2合法k 0b100001连续空格段是 4合法但j | k 0b101101从左到右看空格段变成 1、1、1全是奇数非法。也就是说j 和 k 各自内部没问题但合并之后原本分开的空格段被两边的 1 重新切分产生了长度为奇数的空段。所以转移判断里必须用valid[j | k]这个合并结果不能偷懒。4.3 多组数据下忘记清空状态表题目是多组输入直到 0 0 结束。如果使用全局数组每组数据之间一定要清空尤其是 f 数组和转移表。很多人在单组数据上跑对了一提交就 WA就是因为上一组数据残留的状态污染了下一组。我推荐的写法是直接在 while 循环内部定义局部 vector这样每组数据都会重新分配内存天然避免残留问题。如果为了性能必须用全局数组那就在每组数据开头 memset并且记得每组用新的 n 重新预处理 valid。还有一个隐蔽的地方滚动数组里f.swap(nxt)之后nxt 里面装的是旧 f 的值。下一轮循环开始前必须fill(nxt.begin(), nxt.end(), 0)。否则旧值没清干净会把不存在的方案算进去。这个我在代码里专门处理了但如果你自己写的时候用的是三个数组或者固定数组也要注意类似问题。4.4 交换 n 和 m 的时机当 N M 时交换棋盘是常见优化。但交换之后一定要记得状态位数是交换后的 n阶段数是交换后的 m。后面枚举所有状态写1 n阶段循环写i m。如果哪边搞反了轻则数组越界重则答案错得非常离谱。另外有些题目里横块和竖块的长度可能不一样或者棋盘不是矩形这时候能不能直接交换 n 和 m 要额外判断。但在这道题里因为 1*2 方块本身可以旋转所以旋转棋盘不影响方案数放心交换。5. 从蒙德里安到其他状压题这套思路还能怎么用5.1 识别“列间决策 列内约束”的题目做完蒙德里安的梦想之后我对状态压缩 DP 的一个最大体会是位运算只是工具建模才是核心。这道题能状态压缩是因为它的决策天然具有“按列推进”的结构。每一列的摆放只影响下一列而且这种影响可以被一个 N 位二进制数完整描述。类似地很多棋盘覆盖、放置方案计数、连通性判断的题如果满足“相邻两列之间的约束可以压缩成一个状态”就可以照猫画虎地做。经典的玉米田、铺地砖、炮兵阵地这类题本质套路都很像先枚举当前层状态再枚举上一层状态用位运算判断冲突最后累加方案数。差别只在于状态含义和转移条件。5.2 更进一步的优化转移表、滚动数组、矩阵快速幂蒙德里安这道题 m 也只有 11所以不需要花里胡哨的优化。但如果以后遇到 n 很小、m 很大的版本比如 n 6m 10^9转移就是一个线性递推完全可以用矩阵快速幂把时间复杂度变成 O(2^{3n} log m)。这时候预处理出来的 trans 表就相当于转移矩阵DP 的累加过程就是矩阵乘法。滚动数组则更适合当前这种只需要最后一列答案的题。因为它只保留了上一阶段的状态空间从 O(m * 2^n) 降到 O(2^n)对于 n 更大一点的题目非常有用。5.3 和轮廓线 DP、插头 DP 的关系如果继续往下学会碰到轮廓线 DP 和插头 DP。蒙德里安的梦想其实就是最简单的一种轮廓线 DP只是扫描单位从“一行”变成了“一列”状态从“整列向外伸出的位置”变成了“当前轮廓线上的占用状态”。插头 DP 维护的信息更细除了这一格有没有被占用还要记录插头之间的连通关系用来处理回路、哈密顿路径等问题。但底层思想和蒙德里安一致找到一种紧凑的状态把相邻阶段之间的影响完整传递下去。所以别把这题只当成一个孤立题解。它的建模方式、位运算细节、预处理技巧在后面的状压、轮廓线题目里都会反复出现。真正理解了“横块伸出去”这个视角再看到类似题时你会比没做过的人少走很多弯路。最后说一点个人体会状态压缩 DP 的题目代码往往不长难的是想出那个状态。蒙德里安的梦想算是少数几道“想通状态就赢一半”的题。如果你现在还在状态定义里绕不要急着背代码先拿一张纸画一画 2*4 棋盘把每一种方案按列拆开观察横块是怎么“伸过去”的。这一步一旦通了后面所有转移条件都是顺理成章的事。