AC自动机+矩阵快速幂：DNA序列计数问题全解析

1. 从一道题看字符串匹配的进阶玩法

DNA Sequence POJ - 2778 这道题，在算法竞赛圈子里算是经典中的经典。它把 AC 自动机和矩阵快速幂这两个看起来不太搭边的东西捏在了一起，解决了一个非常实际的问题：给定若干禁止出现的模式串，问长度为 n 的字符串中，不包含任何禁止模式串的方案数有多少。这个问题表面上是在数 DNA 序列，实际上是一类通用的“带约束的路径计数”问题。

我第一次接触这道题的时候，第一反应是 DP：设 dp[i][j] 表示长度为 i、当前在 AC 自动机上走到节点 j 的方案数，转移就是枚举下一个字符，沿着 fail 树走一步。这个思路本身没问题，但 n 可以大到 2×10^9，线性 DP 直接超时。这时候矩阵快速幂就派上用场了——因为状态转移是线性的、每步都一样，正好可以用矩阵来刻画。

这篇文章我会把这道题从头到尾拆一遍：AC 自动机怎么建、fail 指针为什么这么跳、矩阵怎么构造、快速幂怎么写、有哪些坑容易踩。适合已经会写基础 AC 自动机、但对矩阵加速 DP 还不太熟的读者，也适合想复习字符串自动机 + 矩阵优化这套组合拳的老手。读完你不仅能拿下这道题，还能把“自动机上跑矩阵”这个套路迁移到其他计数问题上。

2. 问题本质与整体设计思路

2.1 题目到底在问什么

先把题意翻译成人话。给定 m 个模式串（只含 A、C、G、T 四种字符），问有多少个长度为 n 的字符串，不包含任何一个模式串作为子串。答案对 100000 取模。

举个例子，如果禁止串是 "AT"，n=2，那么所有长度为 2 的串里，只要出现连续的 "AT" 就不算。我们要数的是“安全串”的数量。

这个问题的核心难点有两个：一是如何高效判断一个串是否包含禁止子串，二是 n 太大不能线性递推。前者用 AC 自动机解决，后者用矩阵快速幂解决。

2.2 为什么选 AC 自动机而不是 KMP 或后缀自动机

多模式串匹配，第一反应就是 AC 自动机。KMP 只能处理单模式串，你要对每个模式串分别跑一遍，复杂度是 O(n·m)，而且没法把“当前匹配到哪个前缀”这个状态统一起来。后缀自动机更适合处理子串统计类问题，但它的状态转移不是按字符逐位走的，构造矩阵不直观。

AC 自动机的优势在于：它把所有模式串的前缀合并成一棵 Trie 树，每个节点代表“当前已经匹配到的最长前缀”。你在上面走一步，就相当于读入一个字符，状态转移是确定的、有限的。这正好满足矩阵快速幂的要求——状态数有限、转移规则固定。

2.3 矩阵快速幂为什么能加速

线性 DP 的一般形式是：dp[i+1][to] += dp[i][from] × trans[from][to]。如果 trans 不随 i 变化，那么从 dp[0] 到 dp[n] 就是 trans 这个矩阵的 n 次幂作用在初始向量上。

矩阵乘法满足结合律，所以可以用快速幂把 O(n) 次转移压缩成 O(log n) 次矩阵乘法。每次矩阵乘法是 O(S^3)，S 是状态数。这道题里 S 最多是模式串总长度加一，通常不超过 100，所以 S^3 大概 10^6，log n 大概 30，总共 3×10^7 次运算，完全能接受。

注意：矩阵快速幂的前提是转移矩阵固定。如果每步转移规则不一样，就不能用。这道题里每个位置可以放 4 种字符，规则完全一致，所以适用。

2.4 整体流程拆解

整个算法的流程可以分成四步：

1. 把所有模式串插入 Trie 树，标记终止节点。
2. 构建 fail 指针，同时把终止标记沿着 fail 树传递下去（因为一个节点的 fail 指向的节点如果是终止节点，那这个节点也危险）。
3. 根据 AC 自动机构造转移矩阵：从每个安全节点出发，枚举 4 个字符，走到下一个节点，如果下一个节点安全，就在矩阵对应位置加一。
4. 对矩阵求 n 次幂，把初始状态（根节点）那一行的所有列加起来，就是答案。

这四步里，第一步和第二步是 AC 自动机的标准操作，第三步是本题的关键转化，第四步是矩阵快速幂的模板。

3. AC 自动机构建的核心细节

3.1 Trie 树的插入与终止标记

插入模式串的代码很标准，每个节点维护一个 next[4] 数组和一个 fail 指针，外加一个 flag 表示是否是禁止节点。字符映射我用的是 A→0，C→1，G→2，T→3，用一个 map 数组转换。

int get_id(char c) { if (c == 'A') return 0; if (c == 'C') return 1; if (c == 'G') return 2; return 3; } void insert(char *s) { int p = 0; for (int i = 0; s[i]; i++) { int c = get_id(s[i]); if (!next[p][c]) next[p][c] = ++tot; p = next[p][c]; } flag[p] = 1; // 标记终止节点 }

这里有个细节：如果多个模式串有相同前缀，Trie 树会自动合并，不会重复建节点。这也是 AC 自动机比逐个匹配高效的原因之一。

3.2 fail 指针的构建与终止标记传递

fail 指针的构建用 BFS。根节点的所有儿子 fail 指向根，然后逐层往下。核心逻辑是：对于节点 u 的字符 c 儿子 v，如果 u 的 fail 指针指向的节点也有字符 c 儿子，那 v 的 fail 就指向那个儿子；否则继续沿着 fail 往上找，直到根节点。

void build() { queue<int> q; for (int c = 0; c < 4; c++) { if (next[0][c]) { fail[next[0][c]] = 0; q.push(next[0][c]); } } while (!q.empty()) { int u = q.front(); q.pop(); flag[u] |= flag[fail[u]]; // 关键：传递禁止标记 for (int c = 0; c < 4; c++) { int v = next[u][c]; if (v) { fail[v] = next[fail[u]][c]; q.push(v); } else { next[u][c] = next[fail[u]][c]; // 路径压缩 } } } }

这里有两个重点。第一，flag[u] |= flag[fail[u]]这一行必须在出队时执行，保证 fail 链上所有祖先的禁止标记都传递到当前节点。第二，next[u][c] = next[fail[u]][c]这行是路径压缩，把不存在的边直接指向 fail 链上的下一个节点，这样后续转移时不用再沿着 fail 跳，直接 O(1) 就能找到下一个状态。

提示：路径压缩之后，Trie 树的结构被改变了，原来的空边变成了指向 fail 链的边。这在构造转移矩阵时非常方便，因为每个节点对每个字符都有唯一的下一跳。

3.3 哪些节点是“安全”的

一个节点是安全的，当且仅当它本身不是终止节点，且它的 fail 链上没有任何终止节点。经过上面的标记传递，我们只需要判断flag[u] == 0即可。

为什么 fail 链上有终止节点就不安全？因为 fail 指针指向的是当前匹配串的最长真后缀。如果这个后缀是一个禁止串，那当前串就包含了禁止串作为子串，自然不合法。

举个例子：禁止串是 "AT"，当前匹配到 "GAT"，节点代表 "GAT" 这个前缀。它的 fail 指向 "AT" 对应的节点，而 "AT" 是终止节点，所以 "GAT" 也危险。标记传递就是把这个危险信号沿着 fail 链传下去。

3.4 节点编号与状态数的确定

节点编号从 0 开始，0 是根节点。总节点数 tot 在插入完成后确定，之后不会再增加。构造矩阵时，状态数就是 tot+1。注意，只有安全节点才参与矩阵构造，危险节点直接跳过。

这里有个容易踩的坑：路径压缩之后，next 数组的值可能指向任意节点，包括危险节点。构造矩阵时要判断目标节点是否安全，不安全就不加边。

4. 转移矩阵的构造与快速幂实现

4.1 矩阵规模与初始化

设安全节点有 S 个，我们构造一个 S×S 的矩阵 M。M[i][j] 表示从安全节点 i 走一步到达安全节点 j 的方案数。因为每个节点可以放 4 种字符，所以每个节点的出度最多是 4。

初始向量其实就是一个长度为 S 的向量，只有根节点对应的位置是 1，其余是 0。但我们可以不显式地写向量，直接算矩阵的 n 次幂，然后把根节点那一行的所有元素加起来。

struct Matrix { long long a[MAXN][MAXN]; Matrix() { memset(a, 0, sizeof(a)); } }; Matrix mul(Matrix x, Matrix y, int sz) { Matrix res; for (int i = 0; i < sz; i++) for (int k = 0; k < sz; k++) { if (x.a[i][k] == 0) continue; for (int j = 0; j < sz; j++) { res.a[i][j] = (res.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD; } } return res; }

这个乘法我加了一个小优化：如果 x.a[i][k] 是 0 就跳过。因为转移矩阵通常比较稀疏，这个优化能省不少时间。

4.2 从 AC 自动机到矩阵的映射

构造矩阵的代码很直接：遍历所有安全节点，对每个节点枚举 4 个字符，找到下一跳，如果下一跳也安全，就在矩阵对应位置加一。

int id[MAXN]; // 安全节点的重新编号 int sz = 0; for (int i = 0; i <= tot; i++) { if (!flag[i]) id[i] = sz++; } Matrix M; for (int i = 0; i <= tot; i++) { if (flag[i]) continue; for (int c = 0; c < 4; c++) { int j = next[i][c]; if (flag[j]) continue; M.a[id[i]][id[j]]++; } }

注意这里用的是重新编号后的 id，因为危险节点不参与矩阵，直接跳过会让编号不连续。重新编号之后，矩阵规模就是安全节点的数量。

注意：如果根节点本身是禁止节点（比如模式串是空串），那整个问题答案就是 0。但题目通常不会给空串，这里只是提一下边界情况。

4.3 矩阵快速幂的写法

快速幂的模板很固定，就是二进制拆分指数，不断平方。

Matrix qpow(Matrix base, int exp, int sz) { Matrix res; for (int i = 0; i < sz; i++) res.a[i][i] = 1; // 单位矩阵 while (exp) { if (exp & 1) res = mul(res, base, sz); base = mul(base, base, sz); exp >>= 1; } return res; }

这里 exp 是 n，也就是字符串长度。初始矩阵是单位矩阵，然后不断平方。最后把结果矩阵的第 id[0] 行（根节点对应的行）所有元素加起来，就是答案。

4.4 答案的提取与取模

答案提取很简单：

long long ans = 0; int root = id[0]; for (int j = 0; j < sz; j++) { ans = (ans + res.a[root][j]) % MOD; } printf("%lld\n", ans);

为什么是根节点那一行？因为初始状态是根节点，长度为 0 时只有根节点有 1 种方案。经过 n 步转移后，根节点到每个安全节点的方案数就是那一行的元素。把所有安全节点的方案数加起来，就是长度为 n 且不包含禁止串的字符串总数。

5. 实操中的常见问题与排查技巧

5.1 数组开多大才够

这道题的节点数上限是模式串总长度加一。如果 m 个模式串，每个长度不超过 10，那总长度最多 100，节点数最多 101。矩阵是 101×101，用 long long 存的话大概 80KB，完全没问题。

但如果你不确定数据范围，建议开大一点，比如 MAXN = 110 或 120。开太小会 RE 或者 WA，开太大浪费内存但不会出错。

5.2 取模为什么是 100000

题目要求对 100000 取模，不是常见的 1e9+7。这个模数比较小，矩阵乘法时中间结果可能溢出 int，所以要用 long long。另外，100000 不是质数，但这道题只涉及加法和乘法，不涉及除法，所以不影响。

5.3 fail 指针构建时的顺序问题

fail 指针必须用 BFS 按层构建，不能 DFS。因为 fail 指针指向的节点深度一定比当前节点小，BFS 保证处理当前节点时，它 fail 指向的节点已经处理完了。

另外，flag[u] |= flag[fail[u]]这行必须在出队时执行，不能在入队时执行。因为入队时 fail 指针可能还没设置好。

5.4 路径压缩的副作用

路径压缩把空边指向了 fail 链上的节点，这会让 Trie 树变成一张图。如果你后续还要用 Trie 树做其他操作（比如统计前缀出现次数），可能会受影响。但在这道题里，路径压缩只有好处没有坏处，因为它让状态转移变成 O(1)。

5.5 矩阵乘法的优化技巧

矩阵乘法是 O(S^3)，如果 S=100，一次乘法就是 10^6 次运算。快速幂要做 log n 次乘法，大概 30 次，总共 3×10^7 次。这个量级在 C++ 里大概几百毫秒，能过。

但如果 S 更大，比如 200，那一次乘法就是 8×10^6，30 次就是 2.4×10^8，可能会超时。这时候可以用一些优化：

• 稀疏矩阵优化：如果矩阵很稀疏，可以只存非零元素。
• 循环顺序优化：把 k 循环放外面，利用缓存局部性。
• 位运算优化：如果模数是 2 的幂，可以用位运算代替取模。

这道题里 S 通常不超过 100，不需要这些优化。

5.6 常见错误速查表

提示：如果 n=0，答案应该是 1（空串），但题目通常 n≥1。如果遇到 n=0 的情况，快速幂返回单位矩阵，根节点那一行只有根节点自己是 1，加起来就是 1，正好正确。

6. 从这道题延伸出的通用套路

6.1 自动机上跑矩阵的适用条件

这套方法不是只能用在 AC 自动机上。任何有限状态自动机，只要满足以下条件，都可以用矩阵快速幂加速：

1. 状态数有限且固定。
2. 转移规则不随步数变化。
3. 问题是线性递推的计数问题。

比如，你可以用同样的方法解决“长度为 n 的字符串中不包含某些子序列的方案数”，只需要把 AC 自动机换成子序列自动机。或者“在图上走 n 步不经过某些点的方案数”，只需要把 AC 自动机换成图的邻接矩阵。

6.2 矩阵构造的通用模板

矩阵构造的通用模板是：对于每个状态 i，枚举所有可能的转移，如果转移合法（目标状态安全），就在 M[i][j] 上加一。这个模板适用于所有自动机 + 矩阵快速幂的题目。

关键点在于“安全”的定义。在 AC 自动机里，安全意味着不在 fail 链上遇到终止节点。在子序列自动机里，安全意味着不匹配任何禁止子序列。在图里，安全意味着不经过禁止点。

6.3 复杂度分析与优化方向

这道题的时间复杂度是 O(S^3 log n)，空间复杂度是 O(S^2)。S 是安全节点数，n 是字符串长度。

如果 S 很大，可以考虑以下优化：

• 用稀疏矩阵存储，只存非零元素。
• 用快速幂的变体，比如二进制拆分时只算需要的幂次。
• 用特征多项式或线性递推优化，把 O(S^3 log n) 降到 O(S^3 + S^2 log n)。

但这些优化在这道题里不需要，因为 S 很小。

6.4 类似题目推荐

如果你掌握了这道题，可以试试以下类似题目：

• 在 AC 自动机上跑矩阵，统计包含至少一个模式串的方案数（用总数减去不包含的）。
• 在 AC 自动机上跑矩阵，统计每个模式串出现的期望次数。
• 在图上跑矩阵，统计从起点到终点走 n 步的方案数。

这些题目的核心思路都一样：把状态转移写成矩阵，然后用快速幂加速。

7. 我个人在实际操作中的几点体会

这道题我前前后后写了三遍才完全搞明白。第一遍是 WA，因为忘了传递禁止标记；第二遍是 RE，因为数组开太小；第三遍才 AC。

最大的体会是：AC 自动机的 fail 指针和终止标记传递是这道题的核心，如果这一步错了，后面矩阵构造得再对也没用。建议在写矩阵之前，先手动模拟一个小例子，确认每个节点的 flag 和 next 数组都正确。

另外，矩阵快速幂的模板最好背下来，因为很多题都要用。我习惯把矩阵乘法和快速幂写成两个独立函数，这样调试的时候方便单独测试。

最后分享一个小技巧：如果答案不对，可以先输出矩阵的前几行和前几列，看看转移关系是否符合预期。这个方法帮我省了很多调试时间。