递推到O(logn)的建模实战)
先放个结论在开头P8624 这道题真正想让你掌握的不是骰子有多少种叠法而是怎么把一眼看过去是 O(n) 的递推加速成 O(log n)。题目本身来自蓝桥杯 2015 省 AB 组n 最大能到 10^9普通 for 循环必挂而骰子六个面加上四个侧面朝向恰好又是一个很典型的“状态 关系”图结构。只要能把相邻两个骰子之间的合法关系写成矩阵这道题就成功了大半。我当时的一大感受是递推式人人会列真正卡住大家的永远是矩阵构造那一步所以这篇文章会用最笨的拆解方式把整条链路讲透。适合刚学矩阵快速幂、或者刷题时总在最后一步取模/矩阵相乘出 bug 的朋友。先说明一下这不是一道纯数学公式题也不是数论题。它的核心是建模把“垒骰子”的过程变成状态转移再用矩阵幂一次性算完。理解了这一点你后面遇到类似的走迷宫、自动机、图路径计数问题都能复用同一套模板。1. 题目考点拆解与整体设计思路1.1 先读懂题目到底在限制什么题面里最关键的信息有两个第一骰子的 1 和 4、2 和 5、3 和 6 是相对的面这是常识第二把骰子垒起来时如果两个骰子贴在一起的面上点数之和等于 5那么这两个面就不能接触。举个例子一个骰子朝下的面是 1那它下面的那个骰子朝上的面就不能是 4因为 1 4 5。但如果是 1 和 3和是 4完全没问题。所以规则不是“某个数字不能见面”而是“每一组贴脸都要满足点数和大于等于 5”等价于点数和不等于 5。这里容易忽略的是题目问的是“四个侧面都被认为是不同的方向”也就是说每个骰子垒好后还可以绕垂直轴转 4 次。所以最终答案要乘上 4 的 n 次方。这个坑我在第一次做的时候漏掉了写完答案才发现样例都对不上。1.2 为什么 O(n) 递推一定会超时很多同学一看到 n 个骰子就想到 DP设 f[i][j] 表示第 i 个骰子朝上的面是 j 时的方案数然后枚举第 i 个骰子朝下面的点数和第 i - 1 个骰子朝上面的点数满足条件就累加。这个思路完全正确时间复杂度是 O(n * 6 * 6)也就是 36n。问题在于 n 可以到 10 的 9 次方。就算你每次循环只做一次加法1e9 次操作在普通 OJ 上也已经接近极限再加上矩阵计算常用的取模运算基本稳定超时。所以必须把“递推 n 次”压缩成“矩阵的 n - 1 次幂”把复杂度降到 O(6^3 log n)。这也是矩阵快速幂最常见的应用场景递推关系是线性的、状态数很小、但是步数极大。1.3 状态转移的抽象从骰子到图六个面每个面都能作为骰子朝上的面所以状态数就是 6。相邻两个骰子之间能否接触取决于上一个骰子的上面和下一个骰子的下面。这里有一个关键转换下一个骰子的下面不是随便选的它和下一个骰子的上面是对面关系。也就是说如果下一个骰子朝上的面是 j那它朝下的面是 op[j]。要判断两个骰子能不能叠在一起看的其实是上一个骰子的上面 i 和下一个骰子的下面 op[j] 是否冲突。于是我们可以构造一个有向图节点是骰子的朝上面点数 1 到 6如果 i 到 j 有一条边就表示“上一个骰子朝上的面是 i下一个骰子朝上的面可以是 j”。这条边的存在条件是 i op[j] 不等于 5。你甚至可以把它看成一张 6 个节点的邻接矩阵矩阵里对应位置是 1 或 0。1.4 四个侧面朝向为什么最后乘一个幂就行很多题解直接说答案要乘 4^n但没有解释为什么不是乘 4n也不是在递推过程中乘。原因在于每个骰子独立看都有四个侧面方向可选而且选择侧面方向不会影响相邻接触面的合法关系。想象每个骰子都是一个圆柱体绕垂直轴转约束只发生在上下两个接触面和侧面朝向完全无关。那么 n 个骰子各自有 4 种旋转方式总共就是 4 的 n 次方种。因为这是组合里的乘法原理不是加法所以必须用快速幂单独计算。不过要注意这个乘 4^n 的前提是你算出的“上下状态方案数”不包含侧面旋转信息。如果你一开始就把侧面旋转算进状态答案会重复计数。我个人的习惯是先只算上下点数方案最后再把 pow(4, n) 乘进去。2. 矩阵快速幂的表达与实现细节2.1 为什么要反复取模模数是 1e97也就是 10 的 9 次方加 7。这个数本身不是超过所有 int 范围但两个在模数范围内的数相乘结果会达到 10^18 级别超过 32 位整数上限。所以代码里所有乘法都要用 long long 承接。我见过不少新手在矩阵乘法里写 int结果乘法一多就溢出AC 变 WA。这里有个简单判断标准只要代码里出现 a[i][k] * b[k][j] 且模数约 1e9就必须用 long long。如果你想更保险乘完立刻取模不要等累加完再取。typedef long long ll; const ll MOD 1000000007LL;另外取模是线性友好的也就是 (a b) % MOD 等于 (a % MOD b % MOD) % MOD乘法同理。矩阵乘法本质是一堆乘法再一堆加法所以每步取模不会影响最终正确性。2.2 矩阵乘法的两种姿势矩阵快速幂里要用到两种矩阵乘法矩阵乘矩阵以及矩阵乘向量。前者用于快速幂的倍增过程后者用于最后把转移矩阵应用在初始状态上。我的模板里习惯让矩阵下标从 0 开始还是从 1 开始这道题我会故意用 1 到 6因为骰子点数就是 1 到 6下标 0 直接弃用代码更好读。矩阵乘矩阵的核心是三重循环。为了稍微减掉一点常数可以把循环顺序改成 i, k, j并提前跳过 a[i][k] 为 0 的情况。矩阵规模只有 7x7性能差别不大但养成习惯没坏处。vectorvectorll mul(const vectorvectorll a, const vectorvectorll b) { vectorvectorll c(7, vectorll(7, 0)); for (int i 1; i 7; i) { for (int k 1; k 7; k) { if (a[i][k] 0) continue; for (int j 1; j 7; j) { c[i][j] (c[i][j] a[i][k] * b[k][j]) % MOD; } } } return c; }矩阵乘向量同理只是少一维循环。vectorll mul(const vectorvectorll a, const vectorll v) { vectorll res(7, 0); for (int i 1; i 7; i) { for (int k 1; k 7; k) { res[i] (res[i] a[i][k] * v[k]) % MOD; } } return res; }2.3 快速幂模板和整数快速幂一个逻辑整数快速幂是把指数拆成二进制不断把底数平方。矩阵快速幂完全一样只是“乘法”换成了“矩阵乘法”“底数”换成了转移矩阵“结果”初始化为单位矩阵。单位矩阵在对角线上全 1其他位置全 0。任何矩阵乘单位矩阵都等于它自己这对应整数快速幂里 res 初始化为 1。vectorvectorll mpow(vectorvectorll a, ll p) { vectorvectorll res(7, vectorll(7, 0)); for (int i 1; i 7; i) res[i][i] 1; while (p 0) { if (p 1) res mul(res, a); a mul(a, a); p 1; } return res; }这里有个我自己踩过的坑快速幂循环里先写 res mul(res, a)还是先写 a mul(a, a)很多人会记混。我总结出一个记忆方式res 的更新在 p 当前位是 1 时发生a 的自乘每次循环都发生顺序无所谓但千万别漏掉 a 的自乘。3. 关系矩阵的构造方法与完整求解流程3.1 先定义每个点的对立面骰子对立面的关系是题目的隐含条件1 对 42 对 53 对 6。用代码表达就是int op[7] {0, 4, 5, 6, 1, 2, 3};这个数组的含义是 op[1] 4即“当骰子朝上的面是 1 时朝下的面是 4”。注意这里的映射方向不能写反后面判断合法性时要用到。3.2 7x7 转移矩阵的构造转移矩阵 T 的 T[i][j] 表示上一个骰子朝上的面是 i下一个骰子朝上的面是 j这种状态转移是否合法。合法为 1不合法为 0。判断条件就是上一个骰子的上面 i 和下一个骰子的下面 op[j] 的点数和不能等于 5。for (int i 1; i 6; i) { for (int j 1; j 6; j) { if (i op[j] ! 5) { T[i][j] 1; } } }为什么是 i op[j] 而不是 i j因为直接让上一个骰子的上面和下一个骰子的上面相加没有物理意义。骰子接触的是上一个的底面和下一个的顶面这两个面才是实际接触面。如果你把这个地方搞错整个矩阵都会歪掉。3.3 初始向量与矩阵的 n - 1 次幂只有一个骰子时朝上面可以是 1 到 6 任意一面所以初始向量 f 的 6 个分量都是 1。当 n 大于等于 2 时新的向量 f 应该等于 T 作用在 f 上。比如两个骰子的朝上面分布就是 T * f。三个骰子就是 T * (T * f)。所以 n 个骰子需要计算 T 的 n - 1 次幂然后乘上初始向量。ll n, m; cin n m; bool adj[7][7]; while (m--) { int a, b; cin a b; adj[a][b] adj[b][a] true; } vectorvectorll T(7, vectorll(7, 0)); for (int i 1; i 6; i) { for (int j 1; j 6; j) { if (!adj[i][op[j]] !adj[i][j]) { T[i][j] 1; } } }上面的写法结合了输入冲突对。题目说 a b 5 时不能贴等价于输入给出一组“禁止贴脸”的点数。我直接用 adj 数组把禁止面记下来然后构造 T 时跳过这些组合。3.4 完整求解代码#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 1000000007LL; const int S 7; int op[7] {0, 4, 5, 6, 1, 2, 3}; vectorvectorll mul(const vectorvectorll a, const vectorvectorll b) { vectorvectorll c(S, vectorll(S, 0)); for (int i 1; i S; i) { for (int k 1; k S; k) { if (a[i][k] 0) continue; for (int j 1; j S; j) { c[i][j] (c[i][j] a[i][k] * b[k][j]) % MOD; } } } return c; } vectorll mul(const vectorvectorll a, const vectorll v) { vectorll res(S, 0); for (int i 1; i S; i) { for (int k 1; k S; k) { res[i] (res[i] a[i][k] * v[k]) % MOD; } } return res; } vectorvectorll mpow(vectorvectorll a, ll p) { vectorvectorll res(S, vectorll(S, 0)); for (int i 1; i S; i) res[i][i] 1; while (p) { if (p 1) res mul(res, a); a mul(a, a); p 1; } return res; } ll modpow(ll a, ll p) { ll res 1; while (p) { if (p 1) res res * a % MOD; a a * a % MOD; p 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n, m; cin n m; bool bad[7][7] {}; for (int i 0; i m; i) { int x, y; cin x y; bad[x][y] bad[y][x] true; } vectorvectorll T(S, vectorll(S, 0)); for (int i 1; i 6; i) { for (int j 1; j 6; j) { if (!bad[i][op[j]]) { T[i][j] 1; } } } vectorll f(S, 1); if (n 1) { // 只有一个骰子不需要矩阵幂 ll ans 0; for (int i 1; i 6; i) ans f[i]; cout ans * modpow(4, n) % MOD \n; return 0; } T mpow(T, n - 1); f mul(T, f); ll ans 0; for (int i 1; i 6; i) { ans (ans f[i]) % MOD; } ans ans * modpow(4, n) % MOD; cout ans \n; return 0; }这段代码在核心逻辑上已经可以直接提交。唯一要注意的是我判断不合法条件时写的是!bad[i][op[j]]因为题目给的冲突对是“上下面点数和等于 5”。如果输入是 1 4 冲突那么当上一个骰子上面是 1下一个骰子上面 j 的下面 op[j] 4 时就不合法。这正好对应 bad[1][4] true。4. 从样例手算到现场验证4.1 用 n2 和一组冲突手工推一遍假设 n 2禁止面是 1 4 和 4 1。那么这个情况下两个骰子的合法方案应该很好数第一个骰子的上面有 6 种选择第二个骰子的上面要避开所有会让贴面等于 5 的情况。用代码的逻辑走一遍初始向量 f [1, 1, 1, 1, 1, 1]T 的每一行只在冲突点处为 0。两个骰子方案总数就是 T 的每一行中 1 的数量求和。对于冲突面 1 4第一行里 j 满足 op[j] ! 4也就是 j 不等于 1 和 4因为 op[1] 4op[4] 1。所以第一行有 4 个合法状态。其他行没有冲突每行 6 个合法状态。总方案 4 6 6 6 6 6 34。这里只算了上下状态没有乘 4^n。如果 n 2乘上 16 就是 544。这和直接暴力枚举得到的结果一致。做这种题目我强烈建议先写一个 O(n) 循环的暴力版用来对拍小数据。尤其是矩阵构造初期很容易在 op 映射方向、冲突索引上出错暴力对拍能直接揪出来。4.2 为什么矩阵幂次数是 n - 1 而不是 n很多初学者会问为什么不是 T^n 而是 T^(n-1)因为初始向量 f 已经代表第一个骰子的全部状态。每乘一次 T就相当于在已有的柱体顶部再叠一个骰子。所以1 个骰子直接用 f不乘矩阵2 个骰子乘 1 次矩阵n 个骰子乘 n - 1 次矩阵我第一次写的时候用了 T^n导致样例结果偏大。后来把矩阵次数改掉就对了。这个细节在题目注释里不会强调但它直接关系答案正确性。4.3 最后乘 pow(4, n) 的方向矩阵快速幂算完得到的是一个 6 维向量每个分量代表最上面骰子朝上点数为 i 的方案数。把所有分量加起来得到上下状态方案总数这时候再乘 pow(4, n)。如果先把 pow(4, n) 乘进初始向量等价于把旋转信息错误地绑定在第一个骰子状态上结果会重复计数。我自己的习惯是把乘 4^n 放在最后一步单独写一个快速幂函数这样逻辑最清晰也不容易和矩阵快速幂混在一起。5. 五个常见坑与排查思路实录5.1 容易翻车的五个细节第一个坑是 op 数组映射方向。op[1] 4表示 1 的对面是 4。如果你一不小心写成 op[4] 1但仍然用 i op[j] 做判断那判断就完全反了。我的自查方法是先写一行注释“朝下面 op[朝上面]”然后对照骰子实物默念一遍。第二个坑是矩阵下标和点数混用。题目点数 1 到 6但有些模板从 0 开始。如果 T 是 6x6 且下标 0 代表点数 1那矩阵里的所有索引都要做偏移。写错一次后我决定矩阵直接开 7x7下标 0 弃用宁可多浪费一点空间也不让自己被下标换算绕晕。第三个坑是快速幂里单位矩阵忘初始化。res 没有设成单位矩阵结果第一次乘法后就全 0。这个问题很隐蔽因为小样例可能碰巧能过。我现在的模板每次写 mpow 都会先检查 res[1][1] 是否为 1。第四个坑是取模时机。矩阵乘法里如果先累加完再取模中间值会超过 long long 吗两个 1e9 量级的数相乘结果是 1e18再加几次也不会超过 1e19long long 上限约 9e18所以只加几个数还行。但连续累加很多项时仍然不保险最稳妥是每次加法后立刻取模。第五个坑是漏乘 4^n。这个错误在 n 很大时尤其难发现因为答案巨大取模后看不出“少了个因子”的痕迹。我后来会在代码里给所有关键步骤加注释最后输出前自查有没有写ans * modpow(4, n) % MOD。5.2 常见问题速查表症状原因修复方向小样例结果偏大矩阵幂次数多了 1 次检查 n - 1 还是 n结果偏小且不稳定漏乘侧面旋转 4^n最后统一乘 modpow(4, n)矩阵乘法输出全 0单位矩阵没初始化检查 res 对角是否都是 1提交后只有大点挂乘法溢出将所有矩阵元素改为 long long样例过但构造数据挂冲突面关系判断写反检查 i op[j] 是否对应真实贴面5.3 这套模板能直接迁移的三个场景矩阵快速幂的应用远不止骰子。我做完这道题之后最直接的体会是它和“图上走 k 步方案数”是同构的只要把图用邻接矩阵表示那么 A^k 的每个元素就是从点 i 到点 j 恰好走 k 步的方案数。第二个场景是线性递推数列比如斐波那契。把 f[n] f[n-1] f[n-2] 写成 2x2 转移矩阵n 一大就能用相同模板。很多公开题目把这类问题包装成“爬楼梯升级版”“青蛙跳石板”本质都一样。第三个场景是自动机计数比如字符串里不能出现某个模式串。只要你构造出有限状态自动机的状态转移表它就是一个天然的转移矩阵。状态多时矩阵会变大但思路一模一样。我自己现在的习惯是保留一个不依赖 STL 的迷你矩阵模板方便在任何环境里快速复制。矩阵快速幂这东西本质上就是把“步数与状态数”的线性问题压缩成对数级别的计算一旦你形成这种建模直觉它就不再是难题。
