禁止子串建 AC 自动机得到 DFA,删掉危险状态后在安全状态间建重数转移矩阵,矩阵快速幂求长度 n 的合法串数。
OJ: roj
题目 ID: 1705
难度:提高+/省选-
标签:AC自动机矩阵快速幂字符串python
创建: 2026-10-07 16:05
更新: 2026-10-07 16:05
形式化题目
字母表
与原题样例一致:AT、AC、AG、AA 时,位置 A(否则以 A 开头的两位子串必然命中),位置
数据范围:
正解
思路
先想一个能算的小数据做法。 从左往右逐位填字符,每一步只需保证"当前文本的某个后缀不是禁止串"。
把"文本后缀与禁止串前缀的匹配情况"抽成一个状态,设
下面三件事:后缀状态怎么来、递推矩阵怎么建、终点的边界怎么算。
第一步:AC 自动机把"后缀检查"变成走一条状态边。 把所有禁止串建成 Trie, 每个节点代表"某个禁止串的一个前缀"。补上 fail 指针与缺失边之后得到确定的 DFA:
- 状态
:已填文本的最长后缀恰好落在 Trie 的哪个节点上; - 转移
:再填一个字符 ,新文本的后缀对应的状态变成 ; - 危险标记
danger:节点或它的任意 fail 祖先是某个 的结尾。
danger 必须沿 fail 链传递。走到 XAT 这类文本误判为合法。
把缺失边补成 nxt[u][c] = nxt[fail[u]][c] 后,
第二步:删掉危险状态,在安全状态之间建重数矩阵。 一个状态 danger 为真,
说明此刻文本已经含有完整禁止串,再往后填什么都救不回来,直接从图中删掉。
剩下的状态称为安全状态,记个数为
第三步:答案是
用倍增法求
用样例核对一遍。 禁止串是 AT、AC、AG、AA,它们都是长度 A 与 A 的四条儿子。关键在于节点 A 本身不是任何禁止串的结尾
(禁止串都是两位),它安全;A 的四个儿子才是结尾节点,全部 danger。删掉危险节点后剩下
两个安全状态:根与 A。转移是
- 根走
C/T/G都回根(共条边),根走 A到状态A(条边); - 状态
A的四个字符边都落到危险节点,被删掉,所以这一行全。
第 A"(倒数第二位起必须合法),
C/T/G"。这也说明不需要为最后一位做特殊处理,
只要把 A 这样的合法前缀保留为安全状态,矩阵幂自动把结尾的各种情形都数进去了。
关于素材源。 本题与经典题 POJ 2778 DNA Sequence 完全同型(ACTG、模 std.cpp 就是这一算法。已实测它在全部 10 个测试点上与数据一致,
因此本题按其思路独立重写,不照抄。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 16:05
# update_at: 2026-10-07 16:05
import sys
from collections import deque
MOD = 100000 # 答案取模的模数
SHIFT = 64 # 压位矩阵乘法:每个元素占 64 位,一列最多累加 size<=101 次不会进位
MASK = (1 << SHIFT) - 1
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Matrix = list[list[int]] # 方阵,元素已模 MOD
type Trans = list[list[int]] # DFA 转移表,Trans[u][c] 是状态 u 走字符 c 的落点
def build_dfa(pats: list[str]) -> tuple[Trans, list[bool]]:
"""把禁止子串建成 Trie 并补全成 DFA,返回 (转移表 nxt, 危险标记 danger)。
nxt[u][c] 是状态 u 走字符 c 的落点(缺边已用 fail 链补上);
danger[u] 为真表示"根到 u 的路径的某个后缀"是一个完整禁止子串。
"""
code = {'A': 0, 'C': 1, 'T': 2, 'G': 3} # 字符 -> 自动机字母表下标
nxt: list[list[int]] = [[0] * 4] # 0 号状态是根
danger: list[bool] = [False]
for s in pats:
cur = 0
for ch in s:
v = code[ch]
if nxt[cur][v] == 0: # 开新点
nxt[cur][v] = len(nxt)
nxt.append([0] * 4)
danger.append(False)
cur = nxt[cur][v]
danger[cur] = True # 这个状态本身就是一个禁止子串
fail = [0] * len(nxt)
queue = deque()
for c in range(4):
if nxt[0][c]:
queue.append(nxt[0][c]) # 根的儿子失配后回根,fail 已是 0
while queue:
u = queue.popleft()
if danger[fail[u]]: # 后缀里带禁止串,本状态也算危险
danger[u] = True
for c in range(4):
v = nxt[u][c]
if v:
fail[v] = nxt[fail[u]][c] # fail[u] 已补过边,可直接查表
queue.append(v)
else:
nxt[u][c] = nxt[fail[u]][c] # 补边,得到完整 DFA
return nxt, danger
def mat_mul(x: Matrix, y: Matrix) -> Matrix:
"""方阵乘法:把 y 的每行压成一个大整数,一次整数乘法就得到结果的整行。"""
size = len(x)
packed = [sum(v << (SHIFT * j) for j, v in enumerate(row)) for row in y]
out: Matrix = []
for row in x:
acc = 0
for k in range(size):
acc += row[k] * packed[k] # 每个 64 位位段里独立累加 x[i][k]*y[k][j]
out_row: list[int] = []
for j in range(size):
slot = acc >> (SHIFT * j) & MASK # 第 j 个元素的位段
out_row.append(slot % MOD)
out.append(out_row)
return out
def count_legal(nxt: Trans, danger: list[bool], n: int) -> int:
"""长度为 n 且不含禁止子串的串数:在安全状态构成的 DFA 上走 n 步的路径数。"""
safe = [u for u in range(len(nxt)) if not danger[u]]
index = {u: i for i, u in enumerate(safe)} # 状态 -> 压缩编号
size = len(safe)
base: Matrix = [[0] * size for _ in range(size)]
for u in safe:
for c in range(4):
v = nxt[u][c]
if not danger[v]:
base[index[u]][index[v]] += 1 # 同一对状态可能有多条字符边
# base 的 n 次幂:第 index[0] 行之和 = 从根走 n 步落在任意安全状态的串数
res: Matrix = [[int(i == j) for j in range(size)] for i in range(size)]
e = n
while e:
if e & 1:
res = mat_mul(res, base)
e >>= 1
if e:
base = mat_mul(base, base)
return sum(res[index[0]]) % MOD
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
m = int(next(data))
n = int(next(data))
pats = [next(data).decode() for _ in range(m)]
nxt, danger = build_dfa(pats)
root_danger = danger[0] # 空串就命中禁止串时无解(题面不会出现,防御性判断)
print(0 if root_danger else count_legal(nxt, danger, n))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 16:05
* update_at: 2026-10-07 16:05
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 100000; // 答案取模的模数
const int ALPHA = 4; // 字符集大小,A/C/T/G 依次映射成 0/1/2/3
const int MAXNODE = 128; // m<=10 且 |s|<=10,Trie 节点数上界 1+10*10=101,留少量裕量
// Trie 节点:nxt 先当儿子边用,建完 fail 指针后被补成完整的 DFA 转移表
struct Node {
int nxt[ALPHA]; // 从本状态走字符 c 的去处,根固定为 0 号节点
int fail; // 失配指针
char danger; // 本状态的后缀(含自身)是否出现过禁止子串
};
Node trie[MAXNODE]; // 状态 u 就是 trie[u],编号从 0(根)开始
int node_cnt; // 已创建的节点个数,也等于最大编号
ll m; // 禁止子串个数
ll n; // 序列长度
// 矩阵:sz x sz,元素已模 MOD
struct Mat {
int sz;
ll a[MAXNODE][MAXNODE];
};
// 新建一个 Trie 节点(动态化静态:静态大数组 + node_cnt 当分配指针)
int new_node() {
node_cnt++;
for (int c = 0; c < ALPHA; c++) trie[node_cnt].nxt[c] = 0;
trie[node_cnt].fail = 0;
trie[node_cnt].danger = 0;
return node_cnt;
}
// 字符映射:A/C/T/G -> 0/1/2/3,题面保证输入只含这四种字符
int c2i(char c) {
if (c == 'A') return 0;
if (c == 'C') return 1;
if (c == 'T') return 2;
return 3;
}
// 插入全部禁止子串,再用 BFS 建 fail 指针,顺便把 Trie 补成完整 DFA
void build_dfa() {
node_cnt = 0; // 根节点
for (int c = 0; c < ALPHA; c++) trie[0].nxt[c] = 0;
trie[0].fail = 0;
trie[0].danger = 0;
for (int i = 0; i < m; i++) {
char buf[32];
scanf("%31s", buf);
int cur = 0;
for (int j = 0; buf[j]; j++) {
int v = c2i(buf[j]);
if (trie[cur].nxt[v] == 0) trie[cur].nxt[v] = new_node();
cur = trie[cur].nxt[v];
}
trie[cur].danger = 1; // 该状态本身就是一个禁止子串
}
// 根的儿子的 fail 都指向根
queue<int> q;
for (int c = 0; c < ALPHA; c++) {
int v = trie[0].nxt[c];
if (v) {
trie[v].fail = 0;
q.push(v);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
if (trie[trie[u].fail].danger) trie[u].danger = 1; // 后缀里带禁止串也算危险
for (int c = 0; c < ALPHA; c++) {
int v = trie[u].nxt[c];
if (v) {
// fail[u] 已经处理过,它的 nxt[c] 已是 DFA 转移
trie[v].fail = trie[trie[u].fail].nxt[c];
q.push(v);
} else {
trie[u].nxt[c] = trie[trie[u].fail].nxt[c]; // 补边,形成完整 DFA
}
}
}
}
// 方阵乘法,x 的行乘 y 的列,元素模 MOD
Mat mat_mul(const Mat &x, const Mat &y) {
Mat r;
r.sz = x.sz;
for (int i = 0; i < x.sz; i++)
for (int j = 0; j < x.sz; j++) r.a[i][j] = 0;
for (int i = 0; i < x.sz; i++)
for (int k = 0; k < x.sz; k++) {
if (x.a[i][k] == 0) continue;
for (int j = 0; j < x.sz; j++)
r.a[i][j] = (r.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
}
return r;
}
int main() {
if (scanf("%lld %lld", &m, &n) != 2) return 0;
build_dfa();
int total = node_cnt + 1; // 状态编号范围 0..node_cnt
int id[MAXNODE]; // 原状态 -> 压缩后的「安全状态」编号
int K = 0; // 安全状态个数
for (int u = 0; u < total; u++) {
id[u] = -1;
if (!trie[u].danger) id[u] = K++;
}
if (id[0] < 0) { // 根都危险(空串是禁止子串)时无解
printf("0\n");
return 0;
}
// 转移矩阵:只在安全状态之间连边,同一个 (u,v) 有多条字符边就累加
Mat base;
base.sz = K;
for (int i = 0; i < K; i++)
for (int j = 0; j < K; j++) base.a[i][j] = 0;
for (int u = 0; u < total; u++) {
if (trie[u].danger) continue;
for (int c = 0; c < ALPHA; c++) {
int v = trie[u].nxt[c];
if (!trie[v].danger) base.a[id[u]][id[v]]++;
}
}
// 矩阵快速幂求 base^n:base^n[根][v] 表示从根走 n 步停在 v 的合法串数
Mat res;
res.sz = K;
for (int i = 0; i < K; i++)
for (int j = 0; j < K; j++) res.a[i][j] = 0;
for (int i = 0; i < K; i++) res.a[i][i] = 1;
ll e = n;
while (e > 0) {
if (e & 1) res = mat_mul(res, base);
e >>= 1;
if (e > 0) base = mat_mul(base, base);
}
// 答案 = 从根出发走 n 步落在任意安全状态的总方案数
ll ans = 0;
for (int j = 0; j < K; j++) ans = (ans + res.a[id[0]][j]) % MOD;
printf("%lld\n", ans);
return 0;
}复杂度
- 时间:建 AC 自动机
;矩阵快速幂 , 其中 、 。实测最大点( ) C++ 约 0.03 s,限时 1000 ms。 - 空间:转移矩阵
, 时远小于 1 MB,限时 64 MB。 - Python 侧:矩阵乘法把
的每一行压成一个大整数,一次整数乘法就得到结果的一整行, 把 次小整数乘加换成 次大整数乘法,Python 下 10 个点全部在 1 s 内跑完。
总结
- 子串约束 ⟺ 自动机上的路径约束:禁止"含某个模式作为子串",等价于在 AC 自动机的 DFA 上
永不经过带终止标记的状态;
danger沿 fail 链继承这一步不能省。 - 与
无关的递推 ⟺ 矩阵幂: 中 恒定, 也只是 次矩阵乘法。 - 转移矩阵记重数不记布尔值:多个字符落到同一状态要累加,否则会少数。
- 合法前缀要保留:
A这类"是禁止串前缀但不是禁止串本身"的状态必须留下, 它让"结尾恰好把串带向危险"的情形被正确计数,不必单独处理最后一位。 - 模型识别:本题与 POJ 2778 同型,属于 AC 自动机 + 矩阵快速幂的标准套路;
识别出模型后,
这个异常大的范围就是最强的提示。