Tri Tiling这题我当年刷OJ的时候卡了整整一个晚上。HDU-1143、POJ-2663同一个题两个老牌在线评测平台都有收录输入一个n输出3×n矩形用1×2多米诺骨牌铺满的方案数。看起来就是一道简单的递推但那个f[n] 4*f[n-2] - f[n-4]到底怎么来的很多题解都是“显然可得”四个字带过。这篇文章就把铺砖模型、递推推导、状态压缩DP、打表写法一次讲透。1. 题意与第一反应先做面积奇偶性检查1.1 题面到底在说什么题目描述很简短有一个高度固定为3、长度为n的矩形区域用1×2的多米诺骨牌去铺骨牌可以横放也可以竖放要求完全覆盖、不能重叠、不能超出边界问总共有多少种不同的铺法。这个模型太经典了本质就是“小矩形铺砖”问题。n的取值范围通常不超过30输入一直读到-1为止。很多新手拿到题第一件事就是套斐波那契结果越套越乱。我建议先别急着写递推先把模型的约束条件想清楚。因为矩形高度固定是3每一个骨牌面积是2所以整个区域面积3n必须是偶数。3是奇数那n就必须是偶数。这就是这个问题最重要的前置结论n为奇数时答案直接是0。1.2 手动枚举前几项建立序列直觉先别管通项老老实实数一数小规模情况n0空矩形什么都不用铺算1种方案。n2高度3、长度2的矩形可以数出来是3种三块骨牌全部竖放上面两格用一块横骨牌、下面一格竖放上面一格竖放、下面两格用一块横骨牌。n4画一画能数出11种。这个11很重要它是后面验证递推公式是否正确的一个锚点。把前几项列成表n02468方案数131141153从这张表能直接猜出递推f[0]1, f[2]3, f[4]11然后f[6]4*11-341f[8]4*41-11153完全吻合。也就是说f[n] 4*f[n-2] - f[n-4]大概率是正解。但“猜出来”和“推导出来”是两码事。面试、考试、写解题报告都需要把“为什么是4倍减1”讲清楚。1.3 为什么不是简单的3倍关系很多人会想当然n每增加2方案数是不是就是原来的3倍毕竟n2时有3种n4时如果是3×39但实际是11少了2。这说明在长度为4的矩形里存在一些“跨过中间分界线”的嵌套结构不能简单地切成两个长度为2的独立部分。所以递推关系里必然有更复杂的组合在里面。下一步需要一个系统的推导方法而不是继续枚举。2. 递推公式是怎么来的从三个形状开始2.1 引入辅助形状完整矩形、缺角矩形、凸角矩形直接推导f[n]容易绕晕我建议引入两个辅助状态。这有点像动态规划里“加一个维度”的思想把不完整的边界形状记录成状态再从完整形状和辅助形状的关系里消元。定义三种形状A(n)3×n的完整矩形方案数记为a[n]。B(n)3×n矩形右上角往外多凸出一个格子的形状方案数记为b[n]。C(n)3×n矩形右上角缺一个格子的形状方案数记为c[n]。这里的B和C因为矩形左右、上下对称所以不管是左上角缺还是右上角缺计数结果都一样。B和C都有一个面积奇偶性限制B的面积是3n1C的面积是3n-1要让面积能被2整除n必须是奇数。也就是说b[n]和c[n]在n为奇数时才有非零值。这一点在后面递推里会自动体现。2.2 从完整矩形A(n)的最左边一列入手考虑完整的A(n)n为偶数。盯住最左边一列也就是第1列。第1列有三个格子它们怎么被覆盖只有两类情况。第一类第1列的三行全部由横骨牌覆盖每块横骨牌都横跨第1、2列。这样第2列也被三块横骨牌完全占满右边剩下的部分就是一个完整的3×(n−2)矩形方案数是a[n-2]。第二类第1列只放一块横骨牌。因为第1列左边界是墙竖骨牌只能放在第1列内部所以如果横骨牌放在第1行剩下第2、3行用一块竖骨牌盖住如果横骨牌放在第3行剩下第1、2行用一块竖骨牌盖住。为什么横骨牌不能放在第2行因为第2行横放后第1行和第3行各剩一个孤立的格子既没办法再横放会超出第1列或与第2行冲突也没办法用一块竖骨牌同时盖住不相邻的两行。所以第二类恰好只有两种对称情况。第二种情况里横骨牌占掉了第2列的某一行剩下的区域不再是一个完整矩形而是变成了一个“缺角矩形”C(n−1)。具体说把第2列到第n列看成一个3×(n−1)的矩形它的左上角缺了一个格子。于是第二类贡献是2 * c[n-1]。所以第一个方程a[n] a[n-2] 2 * c[n-1]这个方程非常关键它把完整矩形和缺角矩形联系到了一起。2.3 缺角矩形C(n)和凸角矩形B(n)的递推现在看缺角形状C(m)m为奇数。以右上角缺一格为例从左往右看最左边一列第1列的第1行是缺的剩下第2、3行需要覆盖只有两种覆盖方式。方式一用一块竖骨牌盖住第1列的第2、3行。这样第2列完全空出来右边是一个完整的3×(m−1)矩形贡献a[m-1]。方式二第1列的第2、3行分别用一块横骨牌盖住两块横骨牌都伸到第2列。这样第2列的第2、3行也被占掉剩下来的是一个“凸角”形状也就是B(m−2)。为什么不是缺角因为第2列的第1行变成了凸出来的那个格子后面第3列到第m列构成一个3×(m−2)的完整矩形主体。这个形状在面积上刚好是3(m−2)1正好是凸角形状的面积。所以c[m] a[m-1] b[m-2]再看凸角形状B(m)m为奇数。凸出来的那个格子没有别的选择唯一覆盖方式就是放一块横骨牌把它和第1列第1行连起来盖住。于是第1列第1行也被占掉剩下第1列的第2、3行需要覆盖。后续情况和C(m)完全一样要么第1列第2、3行用一块竖骨牌留下完整矩形A(m−1)要么第2、3行分别横放留下凸角形状B(m−2)。所以b[m] a[m-1] b[m-2]对比c和b的方程形式完全一样初始条件也相同m1时C(1)只有1种铺法B(1)也只有1种铺法。因此可以断定b[m] c[m]这个结论大大简化了后面的消元。2.4 消元得到最终递推式把bc代回c的方程得到c[m] a[m-1] c[m-2]再用A(n)的方程反解c[n-1]。由第一个方程c[n-1] (a[n] - a[n-2]) / 2同时也把A(n−2)的方程写出来a[n-2] a[n-4] 2 * c[n-3]所以c[n-3] (a[n-2] - a[n-4]) / 2现在把c[n-1]用递推展开c[n-1] a[n-2] c[n-3] a[n-2] (a[n-2] - a[n-4]) / 2 (3 * a[n-2] - a[n-4]) / 2再代回A(n)的方程a[n] a[n-2] 2 * c[n-1] a[n-2] 3 * a[n-2] - a[n-4] 4 * a[n-2] - a[n-4]这就把那个“4倍减1”干干净净地推出来了。整个过程其实就是在做“设辅助状态→列方程→消元”和高中数学里的递推数列做法一模一样。只要把缺角、凸角这两个辅助形状定义清楚剩下就是纯代数运算。2.5 用状态压缩DP验证递推的正确性如果你不喜欢几何分类还有一个更暴力但更通用的验证方式状态压缩DP。每一列用一个3位二进制掩码表示“有哪些格子被上一列伸过来的横骨牌占掉了”然后枚举当前列的覆盖方式看看它会向下一列伸出去哪些格子。手动写转移容易漏情况我建议用一个小DFS自动生成转移表。核心逻辑是从左到右扫描当前列遇到已经被占的格子就跳过遇到空格子要么竖放一块骨牌伸到下一列要么横放一块骨牌占用当前行和下一行。def gen_trans(mask): # mask表示上一列伸入当前列的格子集合 res set() def dfs(i, nxt): while i 3 and ((mask i) 1): i 1 if i 3: res.add(nxt) return # 竖放当前行被覆盖并伸向下一列 dfs(i 1, nxt | (1 i)) # 横放覆盖当前行和下一行不伸向下一列 if i 1 3 and not ((mask (i 1)) 1): dfs(i 2, nxt) dfs(0, 0) return res然后用这个转移表从状态0出发跑n列最终回到状态0的路径数就是答案。long long dp[35][8]; dp[0][0] 1; vectorint trans[8]; // 预处理 trans[mask] gen_trans(mask) for (int i 1; i n; i) { for (int s 0; s 8; s) { for (int t : trans[s]) { dp[i][t] dp[i - 1][s]; } } } // 答案是 dp[n][0]我自己第一次写这个状态压缩DP去验证递推时跑出1, 3, 11, 41, 153和几何推导完全一致。两条路线互相佐证说明递推公式没毛病。3. 代码实现打表、滚动数组、矩阵快速幂3.1 打表法三行代码解决90%的情况原题n不超过30最稳的写法是直接预处理一张表然后读一个输出一个不需要每次重新算。#include iostream using namespace std; int main() { long long f[31] {0}; f[0] 1; f[2] 3; for (int i 4; i 30; i 2) { f[i] 4 * f[i - 2] - f[i - 4]; } int n; while (cin n n ! -1) { cout f[n] endl; } return 0; }这个写法有几个细节要注意第一f[1]是奇数默认就是0不用单独初始化。第二循环步长必须是2从4开始因为奇数位置永远不更新。第三数组建议用long long虽然n30时int还扛得住但题目如果改大一点int立刻溢出。3.2 不打下整表滚动数组递推如果你不想开数组也可以直接滚动变量。这里设k n / 2令F(k) f(2k)那么递推变成F(k) 4 * F(k-1) - F(k-2)初始值F(0)1, F(1)3。long long triTiling(int n) { if (n % 2 1) return 0; int k n / 2; if (k 0) return 1; long long a 1, b 3; // aF0, bF1 for (int i 2; i k; i) { long long c 4 * b - a; a b; b c; } return b; }这种写法特别适合实际比赛中不想开大数组的场景。注意k0的时候也就是n0答案应该是1而不是去走循环。3.3 如果n变成10^9矩阵快速幂这道题n范围很小但很多变体题会把n放大到10^9级别。这时候线性递推就不够看了得用矩阵快速幂。把二阶递推写成矩阵形式[ F(k) ] [ 4 -1 ] [ F(k-1) ] [ F(k-1) ] [ 1 0 ] [ F(k-2) ]于是[ F(k) ] [ 4 -1 ]^(k-1) [ F(1) ] [ F(k-1) ] [ 1 0 ] * [ F(0) ]矩阵快速幂的核心代码很标准重点提醒一句矩阵里有负数如果题目要求取模必须加上模数再模否则C的负数取模会让你怀疑人生。struct Mat { long long a[2][2]; Mat(bool ident false) { a[0][0] a[0][1] a[1][0] a[1][1] 0; if (ident) { a[0][0] a[1][1] 1; } } }; Mat mul(Mat x, Mat y, long long mod) { Mat r; for (int i 0; i 2; i) for (int j 0; j 2; j) for (int k 0; k 2; k) r.a[i][j] (r.a[i][j] x.a[i][k] * y.a[k][j]) % mod; return r; } Mat mpow(Mat base, long long e, long long mod) { Mat res(true); while (e) { if (e 1) res mul(res, base, mod); base mul(base, base, mod); e 1; } return res; }使用时如果k1直接返回3k1时计算转移矩阵的k−1次方再乘以初始向量。3.4 输入输出老OJ的时区感这类老题目的输入格式基本都是“多组数据以-1结束”。有人会惯性写成读到0结束结果程序一直不退出。还有人会忘记处理n0的情况。我建议把所有边界都先列出来n为负数结束程序n0输出1n为奇数输出0n为偶数递推或矩阵快速幂还有一点输出每一行答案后记得换行OJ对格式非常敏感。实际测下来题目给的样例0 2 3 4 -1应该输出1 3 0 11这四个值刚好覆盖了全部边界情况务必先拿它们验证程序。4. 常见问题与调试实录4.1 奇数输出0被很多人忽略我在调试群里见过太多人问“n3为什么不是某个数”。三行高矩形长度是3时总面积是9是奇数根本铺不满。这个问题只要在代码最前面加一个if (n 1) return 0;就解决了换成矩阵快速幂版本也一样。请一定把它放在所有计算之前别让递推去处理奇数下标否则数组可能会出现奇怪的越界或者脏数据。4.2 初始条件为什么是f[0]1而不是f[0]0从定义看n0是空矩形确实只有1种方案约定俗成是1。更实际的原因是如果没有f[0]1那么递推f[4]4*f[2]-f[0]就算不出11。这里的f[0]不是物理意义而是递推的“地基”。很多题目里的组合计数都把空集计为一种方案这本质上是组合数学里空乘积等于1的思想。4.3 递推式“4倍减1”的减号从何而来我见过有人把递推背成f[n]3*f[n-2]2*f[n-4]理由是“3种基本块加2种4列特殊块”。这个说法不完全对问题出在组合数的重叠部分。正确理解是4倍f(n−2)覆盖了所有“前n−2列完整 最后2列任意3种铺法”的情况但其中包含了大量可以从中间切开、本质上是f(n−4)延伸出来的情况这些被重复计了一次所以要减掉一个f(n−4)。具体到代数上就是我们消元消出来的那个系数-1。如果你记不清推导我建议考试时用前几项反推系数已知f01, f23, f411假设f[n]A*f[n-2]B*f[n-4]带入f641得4111A3B带入f4和f2得113AB解出来A4, B-1。这个方法在考场上能救命。4.4 状态压缩DP里最常见的转移漏洞如果你选择用状态压缩DP而不是递推最容易犯的错误是手写转移的时候漏掉“缺口嵌套”的情况。比如从状态0出发第一列如果先在第0行竖放再在下面两行横放得到的状态是001很多人会漏掉这个状态因为他们只枚举了“竖放、竖放、竖放”或“横放、横放、竖放”这种规整结构。解决这个问题的方法就是不要手写用DFS自动枚举像我上面给的gen_trans函数一样。越是复杂的边界形状越要相信程序枚举不要相信自己脑补。4.5 从Tri Tiling扩展到更一般的铺砖问题弄懂了这道题可以顺带看两个变体2×n矩形用1×2骨牌铺答案是斐波那契数列f[n]f[n-1]f[n-2]n1时是1。4×n矩形情况会更复杂用状态压缩DP仍然可以解状态从3位变成4位但思路完全一样。这类铺砖问题的通用方法论其实是两个一是找出可分割和不可分割的结构建立递推二是直接上状态压缩DP用机器处理所有边界形状。两种方法都要会因为有些题目会要求你输出递推式的推导过程有些题目则会把n放大到必须用矩阵快速幂。最后说个小技巧我后来教别人这道题时总是先让他们画一遍n4的11种铺法画完再讲缺角、凸角的辅助形状理解速度立刻不一样。如果你是在准备考试或者面试建议把“完整矩形/缺角/凸角”这套辅助状态记下来很多棋盘覆盖递推题都能用这个方法快速建方程。最后再强调一遍处理这类老题目提交前先跑一遍0 2 3 4 -1的样例边界过了这题基本就稳了。