把模式串建成 AC 自动机,对每个非终止态列出 E[u]=1+(1/26)ΣE[δ(u,c)] 的线性方程组,模 1e9+7 高斯消元解出根的期望步数。
OJ: roj
题目 ID: 1707
难度:提高+/省选-
标签:字符串AC自动机高斯消元期望DPpython
创建: 2026-10-07 18:09
更新: 2026-10-07 18:09
形式化题目
给定
数据规模:
注意期望是有理数而非整数:例如第三组样例
正解
思路
第一步:把"当前局面"压成有限个状态。 判断是否已经命中、以及接下来会怎么走,
并不需要记住整个
- 把
插入一棵 trie,结点数 ; - BFS 求出每个结点的失配指针
fail,并把转移补全成 DFA:
- 若
的 fail 链上(含 自身)有某个模式串的结尾,则把 标记为终止态: 走到 就意味着已经有 出现在 里了。这个标记沿 fail 链向下传播, 在 BFS 时顺手做掉: if term[fail[u]]: term[u] = True。
第二步:写出期望方程。 设
终止态那一项取
第三步:为什么必须解方程而不是递推。 直觉上"越走越深"似乎能按深度倒推,
但 a 敲 a 仍停在状态 a、敲 b 立即命中、
敲其余
把上式两边乘
未知量个数 pow(a, MOD-2, MOD)。
手算验证样例 1(a、aa(终止)。
从 a 到 a、敲其余 a 敲 a 到终止态、敲其余
左边一式即 a 就等价于从 a 开始
(多花了这一个字符),敲其余
与样例输出一致。同理
与 aa 得 ab 得 aaaaaaaaaa 得
代码
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 10:20
# update_at: 2026-10-07 10:20
import sys
from collections import deque
MOD = 10 ** 9 + 7 # 答案取模的质数
ALPHA = 26 # 字母表大小
LOWER = 97 # ord('a')
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Dfa = list[list[int]] # 补全后的 DFA 转移表 goto[u][c]:状态 u 收到字母 c 后到达的状态
type Matrix = list[list[int]] # 增广矩阵,每行 = k 个系数 + 末尾 1 个常数项
def build_dfa(patterns: list[bytes]) -> tuple[Dfa, list[bool]]:
"""把模式串建成 AC 自动机,返回(补全后的 DFA 转移表, 已命中标记)。
term[u] 为真表示「从根走到 u 的这条路径上,某个模式串是它的后缀」——一旦到达这种状态
就说明已经有 S_i 出现在 T 里了,游戏结束。标记沿 fail 链传播。
"""
trie = [[-1] * ALPHA] # -1 表示该字母没有儿子
term = [False]
for p in patterns:
u = 0
for c in p:
c -= LOWER
if trie[u][c] < 0:
trie[u][c] = len(trie)
trie.append([-1] * ALPHA)
term.append(False)
u = trie[u][c]
term[u] = True
size = len(trie)
goto: Dfa = [[0] * ALPHA for _ in range(size)] # 0 是根,缺儿子时失配回根
fail = [0] * size
for c in range(ALPHA):
v = trie[0][c]
goto[0][c] = v if v > 0 else 0
dq = deque(v for v in goto[0] if v > 0) # 根的儿子的 fail 都是根
while dq:
u = dq.popleft()
if term[fail[u]]:
term[u] = True # fail 链上有模式串结尾 → 自己也已经命中
gu, gf = goto[u], goto[fail[u]] # fail[u] 层次更浅,其 goto 行已算好
for c in range(ALPHA):
v = trie[u][c]
if v > 0:
fail[v] = gf[c]
gu[c] = v
dq.append(v)
else:
gu[c] = gf[c] # 失配转移,补全成 DFA
return goto, term
def first_hit_expectation(goto: Dfa, term: list[bool]) -> int:
"""求从根出发、首次命中的期望步数(模 MOD)。
设 E[u] = 从状态 u(尚未命中)出发还需敲的字符数期望,则每敲一个字符必 +1:
E[u] = 1 + (1/26) * Σ_c (goto[u][c] 已命中 ? 0 : E[goto[u][c]])
两边乘 26 得 26*E[u] - Σ_{未命中的后继} E[后继] = 26,是 k 元线性方程组。
终止态的期望恒为 0,不给它设未知量,故未知量个数 k = 非终止状态数 ≤ 1 + Σ|S_i| ≤ 151。
"""
ids = [-1] * len(goto) # 自动机状态 -> 未知量下标;-1 表示终止态
k = 0
for u in range(len(goto)):
if not term[u]:
ids[u] = k
k += 1
if ids[0] < 0:
return 0 # 根就是终止态(存在空模式串)时无需敲任何字符;题面保证 |S_i| >= 1
mat: Matrix = [[0] * (k + 1) for _ in range(k)]
for i in range(k):
mat[i][i] = ALPHA
mat[i][k] = ALPHA
for u in range(len(goto)):
i = ids[u]
if i < 0:
continue
row = mat[i]
for c in range(ALPHA):
j = ids[goto[u][c]]
if j >= 0:
row[j] -= 1 # 命中后继的期望按 0 计,不入方程
for row in mat:
for j in range(k + 1):
row[j] %= MOD
for col in range(k): # 前向消元,主元列归一化
piv = col
while piv < k and mat[piv][col] == 0:
piv += 1
if piv == k:
continue # 不可达:命中必然会发生,系数矩阵非奇异
if piv != col:
mat[col], mat[piv] = mat[piv], mat[col]
pc = mat[col]
inv = pow(pc[col], MOD - 2, MOD)
for r in range(col + 1, k):
pr = mat[r]
f = pr[col] * inv % MOD
if f:
pr[col:] = [(a - f * b) % MOD for a, b in zip(pr[col:], pc[col:])]
pc[col:] = [v * inv % MOD for v in pc[col:]]
x = [0] * k # 回代:主元行已归一化,x[i] = 常数项 - Σ 已知项
for i in range(k - 1, -1, -1):
row = mat[i]
x[i] = (row[k] - sum(row[j] * x[j] for j in range(i + 1, k))) % MOD
return x[0]
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
T = int(next(data))
out: list[str] = []
for _ in range(T):
n = int(next(data))
patterns = [next(data) for _ in range(n)]
goto, term = build_dfa(patterns)
out.append(str(first_hit_expectation(goto, term)))
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法,用全局数组与手写模消元):
// 1707 敲键盘
// ---------------------------------------------------------------------------
// 题意:给 n 个仅含小写字母的模式串 S_1..S_n。A 君每次在 26 个字母中等概率随机敲一个,
// 一旦某个 S_i 成为已敲出的串 T 的子串就停止。求停止时 |T| 的期望,模 1e9+7 输出。
//
// 做法:AC 自动机 + 模意义高斯消元(在自动机上做「吸收态马尔可夫链」的首次命中期望)。
// 1) 把 S_1..S_n 插进 trie,BFS 求 fail 并把转移补全成 DFA:δ(u,c)。
// 若 u 的 fail 链上(含自身)有模式串结尾,则把 u 标记为终止态(终态及其后代都不可再走)。
// 2) 状态 u 记「当前已敲出的串,其最长「是某模式串前缀」的后缀对应的 trie 结点」。
// 只要没进终止态就说明还没有任何 S_i 出现。设 E[u] = 从状态 u 出发(尚未命中)还需敲的字符数期望。
// 每敲一个字符必然多敲 1 个,再按等概率 1/26 走到 δ(u,c):
// E[u] = 1 + (1/26) * Σ_c ( δ(u,c) 为终止态 ? 0 : E[δ(u,c)] )
// 其中「到终止态」表示这一步就命中并停止,此后不再敲字符,故贡献 0。
// 3) 只给非终止态设未知量(终止态的期望恒为 0,不入方程),把上式两边乘 26 整理成线性方程组:
// 26 * E[u] - Σ_{c: δ(u,c) 非终止} E[δ(u,c)] = 26
// 状态数 ≤ 1 + Σ|S_i| ≤ 1 + 15*10 = 151,模 1e9+7 高斯消元即可。
// 4) 答案 = E[根结点 0](初始一个字符都没敲)。
//
// 复杂度:O(T * 151^3) 时间,O(151^2) 空间;T ≤ 50 时远低于 2s。
//
// 数据规模(题面【提示】):1 ≤ T ≤ 50,1 ≤ n ≤ 15,|S_i| ≤ 10,字符集 = 26 个小写字母。
// ---------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL; // 模数,质数
const int ALPHA = 26; // 字符集大小
const int MAXNODE = 160; // 1 + 15 * 10 = 151 个状态,留裕量
int ch[MAXNODE][ALPHA]; // trie 的原始儿子
int go_[MAXNODE][ALPHA]; // 补全后的 DFA 转移 δ(u, c)
int fail_[MAXNODE]; // 失配指针
bool terminal[MAXNODE]; // u 的 fail 链上(含自身)是否有模式串结尾
int nodes; // trie 结点数(结点 0 为根)
ll A[MAXNODE][MAXNODE + 1]; // 增广矩阵(模意义)
ll x_[MAXNODE]; // 方程组的解
int id_[MAXNODE]; // 自动机状态 -> 未知量下标,-1 表示终止态(不设未知量)
int nVar; // 未知量个数 = 非终止状态数
// 快速幂:求 a^e mod MOD
ll qpow(ll a, ll e) {
ll r = 1;
a %= MOD;
while (e > 0) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
// 清空单个结点的信息
void clearNode(int u) {
for (int c = 0; c < ALPHA; ++c) ch[u][c] = 0;
fail_[u] = 0;
terminal[u] = false;
}
// 读入 n 个模式串建 trie,再 BFS 求 fail 并把转移补全成 DFA
void buildAC(int n) {
nodes = 1;
clearNode(0);
for (int i = 0; i < n; ++i) {
static char s[32];
scanf("%s", s);
int u = 0;
for (int j = 0; s[j]; ++j) {
int c = s[j] - 'a';
if (ch[u][c] == 0) {
ch[u][c] = nodes;
clearNode(nodes);
++nodes;
}
u = ch[u][c];
}
terminal[u] = true; // 模式串结尾
}
// 根结点:没有儿子的字母转移回根
queue<int> q;
for (int c = 0; c < ALPHA; ++c) {
if (ch[0][c] != 0) {
int v = ch[0][c];
fail_[v] = 0;
go_[0][c] = v;
q.push(v);
} else {
go_[0][c] = 0;
}
}
// BFS 逐层处理
while (!q.empty()) {
int u = q.front();
q.pop();
if (terminal[fail_[u]]) terminal[u] = true; // 沿 fail 链传播终止标记
for (int c = 0; c < ALPHA; ++c) {
if (ch[u][c] != 0) {
int v = ch[u][c];
fail_[v] = go_[fail_[u]][c];
go_[u][c] = v;
q.push(v);
} else {
go_[u][c] = go_[fail_[u]][c];
}
}
}
}
// 对当前 AC 自动机建方程并解出 E[0]
ll solve() {
// 给非终止态分配未知量下标
nVar = 0;
for (int u = 0; u < nodes; ++u) id_[u] = terminal[u] ? -1 : nVar++;
// 初始化增广矩阵:26 * E[u] - Σ ... = 26
for (int i = 0; i < nVar; ++i) {
for (int j = 0; j <= nVar; ++j) A[i][j] = 0;
A[i][i] = ALPHA; // 左边 26 * E[u] 的对角项
A[i][nVar] = ALPHA; // 右端常数 26
}
// 填系数:转移到的非终止态系数 -1
for (int u = 0; u < nodes; ++u) {
if (id_[u] < 0) continue;
int i = id_[u];
for (int c = 0; c < ALPHA; ++c) {
int v = go_[u][c];
if (id_[v] >= 0) A[i][id_[v]] = (A[i][id_[v]] - 1 + MOD) % MOD;
}
}
// 高斯消元:前向消元
for (int col = 0; col < nVar; ++col) {
int piv = -1;
for (int r = col; r < nVar; ++r)
if (A[r][col] != 0) { piv = r; break; }
if (piv < 0) continue; // 理论上不会发生
if (piv != col)
for (int j = col; j <= nVar; ++j) swap(A[col][j], A[piv][j]);
ll inv = qpow(A[col][col], MOD - 2);
for (int r = col + 1; r < nVar; ++r) {
if (A[r][col] == 0) continue;
ll f = A[r][col] * inv % MOD;
for (int j = col; j <= nVar; ++j) {
A[r][j] = (A[r][j] - f * A[col][j]) % MOD;
if (A[r][j] < 0) A[r][j] += MOD;
}
}
}
// 回代
for (int i = nVar - 1; i >= 0; --i) {
ll s = A[i][nVar];
for (int j = i + 1; j < nVar; ++j)
if (A[i][j] != 0) s = (s - A[i][j] * x_[j]) % MOD;
s %= MOD;
if (s < 0) s += MOD;
x_[i] = s * qpow(A[i][i], MOD - 2) % MOD;
}
return x_[id_[0]];
}
int main() {
int T;
if (scanf("%d", &T) != 1) return 0;
while (T--) {
int n;
if (scanf("%d", &n) != 1) break;
buildAC(n);
printf("%lld\n", solve());
}
return 0;
}复杂度
- 时间:建自动机
;高斯消元 ,其中 。 每组数据约 次模运算, 顶格时总计约 次,实测 C++ 单点 ms(限时 2000 ms)。 - 空间:增广矩阵
个 long long,加上自动机的转移表,实测峰值 8.3 MB(限时 256 MB)。 - Python 侧风险:同样的算法,
main.py在顶格数据(、 、 ) 上实测约 s,接近 2000 ms 限时;其余数据点均在 s 以内。 若判题机更慢,Python 有 TLE 风险(算法未降级,只是常数大)。
总结
- 期望题遇到有环的状态图,要立刻从"递推"切换到"列方程"。 本题最大的坑是:
AC 自动机的转移含 fail 跳转,状态图不是 DAG,按深度倒推会得到错误的答案;
正解是列出
之间的线性方程组再消元。 - "停止"这个条件要折进边界条件。 把终止态的期望定为
并不给它设未知量, 方程个数就正好等于非终止状态数,既省了变量又天然表达了"到达即结束、不再贡献字符数"。 - AC 自动机是"把无限长的历史压成有限状态"的标准工具。 只需要保留最长的 「某个模式串的前缀」后缀;终止标记沿 fail 链传播,是判定"已命中"的关键一步。
- 模意义高斯消元:模数是质数,除法用费马小定理求逆元;主元列归一化后 回代只需一次减法与一次乘法,写起来最省心。
数据来源说明。 本题素材源目录带 data.py 分层数据生成器,data/ 的 10 个测试点
是自造数据(点 1–4 为边界/结构层,点 7–10 为顶格卡常层),题面则是按
「信息学奥赛一本通 · 高手训练篇」重建的,与官方原题可能存在细节偏差。
其中点 3 的 std.cpp 与本解法同构(AC 自动机 + 模意义高斯消元),已用
/opt/homebrew/bin/g++-16 -O2 编译并在 10 组数据上全部 PASS,故可作参照;
但 main.cpp 是按仓库规范独立重写的,不照抄 std.cpp 的结构。另外,同型经典题
「Magic boy Bi Luo with his excited string problem」(HDU 5836)的约束、模数与本题完全一致,
可交叉印证解法。