最近有同学在群里发来一道题名字叫“ZZH与计数”后台标签写着矩阵加速、动态规划、记忆化搜索。我扫了一眼就知道这题不简单不是因为代码量大而是因为它把竞赛里最常见的几个计数手段全串在一起了先用动态规划建模再用记忆化搜索处理重复计数最后用矩阵加速解决 n 大得离谱的数据范围。这类题目在 OI 和 ACM 里几乎属于“必会套路”但很多人卡在“知道三个技术点”和“能完整写出正确答案”之间。今天我就拿一道典型的 ZZH 计数题把这条链路从暴力递归到矩阵快速幂完整拆开把我踩过的坑全部摆出来。1. 项目概述一道“ZZH与计数”能带出多少东西1.1 三个关键词不是并列关系是一条链路标题里写了三个技术点很多人误以为它们是三种并列做法实际上它们是一条递进链路动态规划是建模核心记忆化搜索是验证和优化手段矩阵加速是最后的大规模解法。先说动态规划。计数题的难点从来不是“数数”这个动作而是怎么把“方案数”拆成若干个不重不漏的子问题。动态规划解决的就是这个事定义一个状态明确转移关系初始值给对剩下的交给递推。再说记忆化搜索。很多人在推转移方程的时候推错原因是对递归过程没有直观感知。记忆化搜索的优点在于它保留了 DFS 的思考方式同时用缓存把重复计算的中间结果记录下来避免重复计数。实际做题时我经常用它写一个“能跑小数据”的版本用来对拍矩阵加速的结果正确性一目了然。最后是矩阵加速。当 n 到 1e9、1e18 这种量级普通 DP 的 O(n * 状态数) 完全不可行。如果状态转移是固定且线性的就可以把转移关系抽象成矩阵用快速幂在 O(状态数^3 * log n) 时间内算出答案。这三个技术点不是让你三选一而是解决同一道题在不同数据范围下的三个层次。1.2 统一的例题后面所有内容都围绕它展开为了防止内容飘在空中我构造一道典型的 ZZH 风格计数题。这类题的特征是给你一个长度为 n 的序列每个位置能填若干种字符再给若干限制问有多少种合法填法。例题设定如下一个长度为 n 的序列每个位置可以填 A、B、C 三种字符要求相邻两个位置字符不能相同且不允许出现 “A 后面紧跟 B” 的情况即不能有子串 AB。n 最大可以到 1e18答案对 1e97 取模。这道题的状态设计非常经典后面我会从最笨的 DFS 一路优化到矩阵快速幂。你可以把它替换成“不出现连续两个 1”、“不能出现某个单词”、“有 k 种颜色相邻不同”等等变体核心逻辑完全一致。1.3 拿到这类题目先问三个问题我在拿到任何计数题时第一件事不是写代码而是先问自己三个问题状态怎么表示通常考虑“当前填到哪里”和“前面留下了什么影响后续的信息”。在例题里影响后续的只有最后一个字符是什么所以状态里至少包含 last 这个维度。转移是否是线性的意思是“从 i 状态转移到 j 状态的方案数是否是固定的一个系数”。如果转移关系和前面若干步有关或者存在取最值、分支判断那就不能直接套矩阵。n 的范围到底多大n 只有 1e5 就老老实实做一维 DPn 到 1e18 就要考虑矩阵加速或找周期n 在 1e7 附近可以考虑 O(n) 的滚动数组。这个判断决定了整套方案。用表格总结一下不同 n 范围的常用策略数据范围推荐做法时间复杂度n 1e3朴素 DFS 回溯指数级仅用于验证n 1e5记忆化搜索或一维 DPO(n * 状态数)n 1e7滚动数组 DPO(n * 状态数)n 1e18矩阵快速幂O(状态数^3 * log n)下一节开始我按这个表从最底层往上写。2. 核心细节拆解从暴力DFS到记忆化搜索2.1 朴素递归是怎么数数的拿到计数题我的第一版代码永远是裸 DFS。它不追求效率但能帮我确认题目意思有没有理解错。思路是从左往右填字符用一个参数记录上一个位置填了什么然后枚举当前位置的合法选择递归到下一层。#include bits/stdc.h using namespace std; const long long MOD 1e9 7; long long dfs(int pos, int last, int n) { if (pos n) return 1; // 填满 n 个位置是一种合法方案 long long ans 0; for (int cur 0; cur 3; cur) { // 0代表A1代表B2代表C if (cur last) continue; // 相邻不能相同 if (last 0 cur 1) continue; // 不能出现 A 后面跟 B ans dfs(pos 1, cur, n); } return ans; } int main() { int n; cin n; cout dfs(0, -1, n) \n; // -1 表示最开始没有上一个字符 return 0; }这段代码的逻辑不复杂每个位置枚举 A、B、C用 last 记录上一位检查两个限制。注意初始时 last 设成 -1这样第一个位置三种字符都能填。这个版本对 n 小于 15 左右还能跑再大一点就明显卡顿。因为每次递归都重新计算大量重复子问题比如填到第 3 位、last 是 A 的状态会被多条路径反复到达。2.2 重复计数从哪来记忆化怎么消重复计数的根源在于从不同前缀走到“同一个 (pos, last) 状态”时后续的方案数是一样的但 DFS 会把这些状态重复算无数次。以例题为例当 pos3、last0 时不管前两位是 BA 还是 CA剩余位置的合法方案数完全一致。我称这种重叠子问题是重复计数的直接来源。解决思路就是加缓存。给每个 (pos, last) 保存一份计算结果下次遇到直接返回。这就是记忆化搜索也叫“带备忘录的 DFS”。#include bits/stdc.h using namespace std; const long long MOD 1e9 7; long long memo[1005][4]; // memo[pos][last] 记录从该状态出发的方案数-1表示未计算 long long dfs(int pos, int last, int n) { if (pos n) return 1; if (memo[pos][last 1] ! -1) return memo[pos][last 1]; long long ans 0; for (int cur 0; cur 3; cur) { if (cur last) continue; if (last 0 cur 1) continue; ans (ans dfs(pos 1, cur, n)) % MOD; } return memo[pos][last 1] ans; } int main() { memset(memo, -1, sizeof(memo)); int n; cin n; cout dfs(0, -1, n) \n; return 0; }记忆化之后每个状态只算一次复杂度从指数级降到 O(n * 状态数)。这里的状态数是 4last 取 -1、0、1、2 的四种情况所以本质上是 O(4n)。注意一个细节memo 数组的第二维我用了 last 1把 last -1 映射到下标 0避免数组负下标。这个映射在后面的矩阵版本里同样重要很多人的错误就是从这里开始的。2.3 记忆化搜索为什么适合做对拍器说完优化我再说一个实际做题时特别好用的习惯用记忆化搜索当“对拍器”。矩阵快速幂代码一旦写错错误往往很隐蔽不是编译不过而是答案错几个数。这时候直接把记忆化搜索版和一个矩阵版放在一起n 取 1 到 20 逐个跑一遍结果不一致就立刻定位问题。我为什么推荐记忆化搜索而不是普通 DP 来对拍因为记忆化搜索的代码结构和 DFS 保持一致几乎不会出现“转移方向写反”这种问题。而且它可以顺手打印每个状态的返回值配合调试输出查看中间状态非常方便。矩阵版一旦出错起码有个可靠参照物。3. 状态压缩与动态规划的线性化3.1 从DFS到DP数组的平移记忆化搜索本质上是从递归角度理解动态规划。它和递推 DP 的区别只是计算顺序不同记忆化是从顶向下DP 是从底向上。把 DFS 改成 DP 的思路很简单用 dp[pos][last] 表示“填完前 pos 个位置且第 pos 个位置字符是 last 的方案数”。转移的时候枚举最后一位 cur检查 cur 和 last 是否冲突。初始值 dp[1][0] dp[1][1] dp[1][2] 1表示长度为 1 时三个字符都合法。然后从 pos2 开始逐位递推long long dp[100005][3]; dp[1][0] dp[1][1] dp[1][2] 1; for (int pos 2; pos n; pos) { for (int last 0; last 3; last) { dp[pos][last] 0; for (int prev 0; prev 3; prev) { if (last prev) continue; // 相邻不同 if (prev 0 last 1) continue; // 不能出现 AB dp[pos][last] (dp[pos][last] dp[pos - 1][prev]) % MOD; } } } long long ans 0; for (int last 0; last 3; last) ans (ans dp[n][last]) % MOD;注意这里的维度是“最后一位字符”。如果你要处理更复杂的限制比如禁止连续三个字符相同那就要记录最后两位字符状态数变成 3*39这个维度自然会变大。3.2 转移方程的矩阵形式n 一旦到 1e18上面的 O(n) 循环就废了。但我们观察发现每一轮转移只和上一轮的状态有关而且转移关系是固定的不随 pos 改变。这就是矩阵加速的信号。定义状态向量 v_pos 为长度为 3 的列向量第 i 个分量表示“第 pos 位字符为 i 的方案数”。那么 v_{pos1} M * v_pos其中 M[i][j] 表示“从字符 j 转移到字符 i”的合法转移系数。逐个看从 Aj0出发不能到 A相邻不同不能到 B禁止 AB只能到 C所以第 0 行第 0 列为 0第 1 行第 0 列为 0第 2 行第 0 列为 1。从 Bj1出发不能到 B可以到 A可以到 C所以第 0 行第 1 列为 1第 1 行第 1 列为 0第 2 行第 1 列为 1。从 Cj2出发不能到 C可以到 A可以到 B所以第 0 行第 2 列为 1第 1 行第 2 列为 1第 2 行第 2 列为 0。于是转移矩阵是M | 0 1 1 | | 0 0 1 | | 1 1 0 |初始向量 v_1 (1, 1, 1)^T。那么 v_n M^(n-1) * v_1最终答案是 v_n 的三个分量之和。到这里问题变成“算一个 3×3 矩阵的 n-1 次幂”这一步用快速幂就是 O(3^3 * log n)n 再大也不怕。3.3 为什么“线性转移”才能用矩阵加速很多人学到了矩阵快速幂的模板但不知道什么情况下能套。我总结一句话状态转移必须是对状态的线性组合。比如例题中“v_{pos1}[0] v_pos[1] v_pos[2]”每个新状态都是旧状态的固定倍数相加这是线性组合。但如果转移里存在“取最小值”“判断奇偶”“必须依赖前两个位置的组合状态”这些非线性条件就得先想办法把条件拆成更多状态。比如禁止连续两个 AA你可以记录“最后一位是什么以及前面是否已经满足条件”然后把条件固定进状态。这就是为什么很多人会把矩阵加速和动态规划建模紧紧联系在一起建模能力强的人才能把各种限制改造成线性转移。4. 矩阵加速的工程实现4.1 矩阵乘法模板与取模细节矩阵加速的代码量不大但坑很多。先给一个通用的矩阵乘法模板#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 1e9 7; struct Matrix { ll a[3][3]; Matrix(bool identity false) { memset(a, 0, sizeof(a)); if (identity) for (int i 0; i 3; i) a[i][i] 1; } }; Matrix multi(const Matrix A, const Matrix B) { Matrix C; for (int i 0; i 3; i) { for (int k 0; k 3; k) { if (A.a[i][k] 0) continue; // 小优化 for (int j 0; j 3; j) { C.a[i][j] (C.a[i][j] A.a[i][k] * B.a[k][j]) % MOD; } } } return C; } Matrix powMat(Matrix base, ll p) { Matrix res(true); // 单位矩阵 while (p 0) { if (p 1) res multi(res, base); base multi(base, base); p 1; } return res; }我特别强调几个细节。第一矩阵乘法里A.a[i][k] * B.a[k][j]的中间结果最大可能到 (1e9)^2 1e18long long 刚好能装下但再乘一次或加多次就可能溢出所以每一步都必须取模。第二循环顺序我故意写成 i-k-j而不是传统的 i-j-k这样可以减少缓存失效同时方便在A.a[i][k]0时跳过内层循环实测在状态数大的时候提升明显。4.2 快速幂怎么算二进制分解的意义矩阵快速幂和普通快速幂的原理完全一样。要算 A^p我们看 p 的二进制表示比如 p13 转成二进制是 1101也就是 A^13 A^8 * A^4 * A^1。每次循环把 base 平方对应二进制位上的 2 的幂次如果当前位是 1就把 base 乘进结果。普通快速幂里结果初始值是 1到了矩阵这里结果初始值就是单位矩阵 I。因为任何矩阵乘 I 等于它本身I 就是矩阵运算里的“1”。这个如果写错比如初始成零矩阵答案会全变成 0。计算答案的完整代码如下int main() { ll n; cin n; if (n 1) { cout 3 \n; // 长度 1 时三个字符都可以 return 0; } Matrix M; M.a[0][0] 0; M.a[0][1] 1; M.a[0][2] 1; M.a[1][0] 0; M.a[1][1] 0; M.a[1][2] 1; M.a[2][0] 1; M.a[2][1] 1; M.a[2][2] 0; Matrix P powMat(M, n - 1); ll v0 1, v1 1, v2 1; // 初始向量 ll ans 0; ll a0 (P.a[0][0] * v0 P.a[0][1] * v1 P.a[0][2] * v2) % MOD; ll a1 (P.a[1][0] * v0 P.a[1][1] * v1 P.a[1][2] * v2) % MOD; ll a2 (P.a[2][0] * v0 P.a[2][1] * v1 P.a[2][2] * v2) % MOD; ans (a0 a1 a2) % MOD; cout ans \n; return 0; }矩阵加速的核心就是把 O(n) 的循环变成 O(log n) 的幂次运算。注意这里 n 是 long long不要用 intn1e18 时 int 会直接溢出。4.3 从“矩阵分块”角度看大状态优化状态数一旦变大比如 10×10 甚至 50×50 的矩阵朴素矩阵乘法的 O(k^3) 就会成为瓶颈。这时有一个非常实用的优化思路矩阵分块。如果把状态按业务含义分成几组转移矩阵会呈现一种分块结构比如M | X Y | | Z W |其中 X、Y、Z、W 分别是更小的子矩阵。分块乘法的好处有两个第一如果某些块恒为 0可以直接跳过第二相同的子矩阵块可以被重复利用。举一个具体场景状态是“当前匹配到模式串的第几个位置 当前字符是几”这种二维状态很容易形成分块结构不同字符之间的转移共用同一个“模式串匹配子矩阵”。另外在工程实现上分块意味着可以按块稀疏存储或者把经常一起使用的块放在连续内存里。我在写作 20×20 以上矩阵时会先用 Python 把矩阵画出来看哪些块是零再决定要不要拆。很多时候零块能省掉一半以上乘法这个收益在大状态时非常可观。5. 常见问题与排查技巧实录5.1 初始向量和答案统计方向搞反这绝对是我见过最多的错误。矩阵乘法的结果 C A * B 中C[i][j] 是 A 的第 i 行和 B 的第 j 列做点积。如果你用行向量 v * M那么答案就是 v 的每个分量乘 M 的对应行如果你用列向量 M * v答案就是 M 的每行乘 v 的对应分量。两者坑点不同。我推荐固定一种写法全部用列向量。状态向量 v 是 3×1转移矩阵 M 是 3×3v_{new} M * v_{old}。这样思路最顺也不容易搞混。计算答案的时候最后用一个临时变量累加 v_n 的所有分量别直接对矩阵元素求和因为矩阵里很多中间值并不是答案。5.2 取模结果出现负数计数题一般要求答案对 MOD 取模但如果代码里有减法比如(a - b) % MODC 里得到的是负数。这里必须转正(a - b MOD) % MOD。我一般是写一个函数ll norm(ll x) { x % MOD; if (x 0) x MOD; return x; }然后所有加减乘都套一下尤其是统计答案时。这个问题在 dfs 版本里不太容易踩到因为基本只用加法但一换到矩阵、容斥、减法统计就很容易翻车。5.3 快速幂里几个低级错误快速幂的坑集中在三个地方。第一res 初始必须是单位矩阵不是零矩阵第二base 每轮循环都要平方也就是base multi(base, base)第三p 的类型必须是 long long且不断右移 p而不是 p--。我踩过的真实案例写快速幂时把res multi(res, base)写在循环外面结果只乘了一次还有一次把p 1写成了p 1变量 p 一直不更新导致死循环。这类问题靠肉眼很难发现最好的办法是直接用 n2、n3 的几个小数据验证。5.4 边界条件n0 和 n1边界条件很多人会丢。以例题为例如果 n1答案就是 3不需要乘矩阵如果 n0答案应该是 1空序列也是一种方案取决于题目定义。矩阵快速幂里如果直接算 M^(n-1)n 为 1 时就是 M^0单位矩阵乘初始向量正好得到 (1,1,1)答案也是 3所以 n1 其实可以不用特判。但为了代码可读性我仍然建议显式处理 n1 这种情况避免以后改状态的时候出问题。5.5 记忆化搜索递归爆栈虽然记忆化搜索很好用但 n 一旦到 1e6 甚至更大递归深度很深容易爆栈。所以我的经验是记忆化搜索只用来对拍、验证小数据正式的大数据版本一定用矩阵快速幂或自底向上的 DP。如果你确实需要记忆化搜索跑大数据可以把递归函数改成显式栈模拟或者用迭代 dp 数组替代。但归根结底这类计数题的最终答案几乎都是矩阵加速记忆化搜索的定位就是一个“正确性参照物”。6. 这类计数题的进阶路线与实战经验6.1 从固定状态到自动机状态例题的状态是“最后一个字符”非常简单。现实中更常见的是禁止多个子串比如“不能出现 ABA也不能出现 BAB”。这时候固定记录最后一位不够因为 ABA 这种模式需要两个字符作为上下文。解决办法是建立自动机用 KMP 的失配指针或 AC 自动机的状态来表示“当前已经匹配到了模式串的哪个前缀”。自动机的每个节点对应一个匹配状态转移就是自动机上的边。这样状态数等于模式串前缀数量照样可以构造转移矩阵做矩阵加速。我之前做过一道题模式串长度是 20字符集大小 26状态数 20×26520矩阵 520×520用分块稀疏优化后仍然能跑。6.2 组合计数与矩阵加速怎么搭配热词里出现了“组合计数”这类题也很多。比如一个序列被分成若干段每段内部满足某种递推段与段之间用组合数衔接。这种题的思路是对每一段用矩阵算出方案数再把所有段的方案数乘起来最后乘上相应的二项式系数。组合数本身可以用预处理阶乘和逆元来做。Java 里我见过不少人喜欢用快速幂算逆元其实本质上就是在模意义下做小数除法。组合数预处理的时间复杂度是 O(n)n 通常比序列长度小得多不会成为瓶颈。重点是记住矩阵负责段内方案组合数负责段间组合两者是乘法关系而不是加法关系。6.3 周期计数找出循环节再加速另一个高频变体是“周期计数”。有些递推关系在模 MOD 下呈周期性比如答案序列的前若干项一个循环此时可以直接对 n 取模到周期长度再用矩阵快速幂算。判断是否有周期可以先用小数据打印前几十项肉眼观察或者用哈希判断。这个方法特别适合“n 极大但状态很小”的题目。但要注意周期不一定从头开始可能有一段“预周期”。比如前 5 项不循环第 6 项起开始循环。处理方式就是先算出预周期部分再把剩余部分按周期截断。这个技巧在字符串相关的计数题里尤其常见。6.4 不算技巧的技巧写个对拍脚本最后分享一个我坚持了很久的习惯每个矩阵快速幂的题我都会写三个版本裸 DFS、记忆化搜索、矩阵加速。然后写一个 shell 脚本把 n 从 1 到 20 全跑一遍对照输出。脚本就几行for n in $(seq 1 20); do a$(./solve_dfs $n) b$(./solve_mat $n) if [ $a ! $b ]; then echo Mismatch at n$n: dfs$a mat$b fi done echo Done别嫌这个步骤烦。矩阵快速幂的代码一旦写错错的答案往往只在一两个测试点出现肉眼很难发现。对拍能在几十秒内把所有小规模结果全部验证省下的调试时间远超写三个版本的时间。我做题这几年“对拍”是我最想推荐给别人但总被忽略的习惯。回到标题本身“ZZH与计数”这类题看着唬人其实核心就三步先把状态定义清楚再用记忆化或递推确认正确性最后用矩阵加速冲刺大数据。这三步踩过的坑我也都摆在上面了。下一次你再遇到计数题别急着套模板先拿出纸笔把转移矩阵量出来答案自然就出来了。