敲键盘

GitHub跳转原题关系图返回列表

把模式串建成 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

形式化题目

给定 nn 个仅由小写英文字母组成的模式串 S1,…,SnS_1, \dots, S_n。A 君每次从 2626 个字母中 等概率随机敲一个字符,敲出的字符依次拼成长串 TT;一旦某个 SiS_i 成为 TT 的子串, 他立即停止。求停止时 ∣T∣|T| 的数学期望,用模 109+710^9+7 的分数形式输出 (若期望为 ab\frac{a}{b},输出 a⋅b−1 mod (109+7)a \cdot b^{-1} \bmod (10^9+7))。

数据规模:1⩽T⩽501 \leqslant T \leqslant 50 组,1⩽n⩽151 \leqslant n \leqslant 15,∣Si∣⩽10|S_i| \leqslant 10。 即所有模式串总长度不超过 150150,字符集固定为 2626 个小写字母。

注意期望是有理数而非整数:例如第三组样例 P={ab,ac}P = \{\texttt{ab}, \texttt{ac}\}, 每敲一个字符有 226\frac{2}{26} 的概率立刻命中,故期望为 262/2=33826^2/2 = 338。

正解

思路

第一步:把"当前局面"压成有限个状态。 判断是否已经命中、以及接下来会怎么走, 并不需要记住整个 TT——只需记住 TT 的最长的、是某个 SiS_i 前缀的后缀。 这正是 AC 自动机的状态定义。于是:

  1. 把 S1,…,SnS_1, \dots, S_n 插入一棵 trie,结点数 m⩽1+∑∣Si∣⩽151m \leqslant 1 + \sum |S_i| \leqslant 151;
  2. BFS 求出每个结点的失配指针 fail,并把转移补全成 DFA:
δ(u,c)={trie 里 u 的 c 儿子,存在;δ(fail(u),c),否则.\delta(u, c) = \begin{cases} \text{trie 里 } u \text{ 的 } c \text{ 儿子}, & \text{存在};\\ \delta(\mathrm{fail}(u), c), & \text{否则}. \end{cases}
  1. 若 uu 的 fail 链上(含 uu 自身)有某个模式串的结尾,则把 uu 标记为终止态: 走到 uu 就意味着已经有 SiS_i 出现在 TT 里了。这个标记沿 fail 链向下传播, 在 BFS 时顺手做掉:if term[fail[u]]: term[u] = True。

第二步:写出期望方程。 设 E[u]E[u] 为「当前 AC 自动机状态是 uu、且尚未命中」时 还需要敲的字符数期望。敲一个字符必然先贡献 11,然后等概率地走到 δ(u,c)\delta(u, c):

E[u]=1+126∑c=az[ δ(u,c) 是终止态 ? 0 : E[δ(u,c)] ],E[终止态]=0.E[u] = 1 + \frac{1}{26}\sum_{c = a}^{z} \bigl[\, \delta(u, c) \text{ 是终止态} \,?\, 0 \,:\, E[\delta(u, c)] \,\bigr], \qquad E[\text{终止态}] = 0 .

终止态那一项取 00,是因为走到它游戏就结束了,不会再多敲字符—— 这就是"吸收态边界条件"。答案即 E[根]E[\text{根}]。

第三步:为什么必须解方程而不是递推。 直觉上"越走越深"似乎能按深度倒推, 但 δ\delta 里含 fail 跳转:状态 uu 可以一步回到更浅的状态(例如模式串为 {ab}\{\texttt{ab}\} 时,从状态 a 敲 a 仍停在状态 a、敲 b 立即命中、 敲其余 2424 个字母回到根)。状态图有环,E[u]E[u] 之间互相依赖,不存在拓扑序, 只能用线性方程组求解。

把上式两边乘 2626,并把终止态(期望恒为 00)从方程组中剔除:

26 E[u]  −  ∑cδ(u,c) 非终止E[δ(u,c)]  =  26.26\,E[u] \;-\; \sum_{\substack{c \\ \delta(u,c) \text{ 非终止}}} E[\delta(u, c)] \;=\; 26 .

未知量个数 kk 恰等于非终止状态数,k⩽151k \leqslant 151。在模 109+710^9+7 下做高斯消元 (主元列归一化后回代),输出 E[根]E[\text{根}] 即可。因为模数是质数, 除法就是乘逆元 pow(a, MOD-2, MOD)。

手算验证样例 1(P={aa}P = \{\texttt{aa}\})。 自动机只有三个状态:根 RR、a、aa(终止)。 从 RR 敲 a 到 a、敲其余 2525 个字母留在 RR;从 a 敲 a 到终止态、敲其余 2525 个回到 RR。 于是

26E[R]−E[a]−25E[R]=26,26E[a]−25E[R]=26,26E[R] - E[\texttt{a}] - 25E[R] = 26, \qquad 26E[\texttt{a}] - 25E[R] = 26,

左边一式即 E[R]=26+E[a]E[R] = 26 + E[\texttt{a}]:从根出发,第一步敲 a 就等价于从 a 开始 (多花了这一个字符),敲其余 2525 个字母则原地重来。把 E[a]=E[R]−26E[\texttt{a}] = E[R] - 26 代回右边一式:

26 (E[R]−26)−25E[R]=26  ⟹  E[R]=262+26=702,26\,(E[R] - 26) - 25E[R] = 26 \;\Longrightarrow\; E[R] = 26^2 + 26 = 702,

与样例输出一致。同理 P={ab}P = \{\texttt{ab}\} 解出 E[R]=262=676E[R] = 26^2 = 676。

与 n=1n = 1 的部分分的关系。 当 n=1n = 1 时可用 Conway 领项公式闭式求解: 期望等于 ∑26∣b∣\sum 26^{|b|},其中 bb 取遍该模式串的所有 border(既是前缀又是后缀的串, 含自身)。对 aa 得 262+26=70226^2 + 26 = 702、对 ab 得 262=67626^2 = 676、 对 aaaaaaaaaa 得 ∑k=11026k≡778451819\sum_{k=1}^{10} 26^k \equiv 778451819,三者都与数据一致—— 这也从另一个方向印证了方程组的建模没有偏。但该公式无法处理多个模式串, 正解仍是 AC 自动机 + 高斯消元。

代码

Python 版:

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++ 版(同一算法,用全局数组与手写模消元):

cpp
// 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;
}

复杂度

  • 时间:建自动机 O(26⋅m)O(26 \cdot m);高斯消元 O(k3)O(k^3),其中 k⩽1+∑∣Si∣⩽151k \leqslant 1 + \sum |S_i| \leqslant 151。 每组数据约 k33≈1.1×106\frac{k^3}{3} \approx 1.1 \times 10^6 次模运算,T=50T = 50 顶格时总计约 5.7×1075.7 \times 10^7 次,实测 C++ 单点 9∼419 \sim 41 ms(限时 2000 ms)。
  • 空间:增广矩阵 O(k2)≈1512O(k^2) \approx 151^2 个 long long,加上自动机的 O(26m)O(26m) 转移表,实测峰值 8.3 MB(限时 256 MB)。
  • Python 侧风险:同样的算法,main.py 在顶格数据(T=50T = 50、n=15n = 15、∣Si∣=10|S_i| = 10) 上实测约 1.71.7 s,接近 2000 ms 限时;其余数据点均在 1.11.1 s 以内。 若判题机更慢,Python 有 TLE 风险(算法未降级,只是常数大)。

总结

  • 期望题遇到有环的状态图,要立刻从"递推"切换到"列方程"。 本题最大的坑是: AC 自动机的转移含 fail 跳转,状态图不是 DAG,按深度倒推会得到错误的答案; 正解是列出 E[u]E[u] 之间的线性方程组再消元。
  • "停止"这个条件要折进边界条件。 把终止态的期望定为 00 并不给它设未知量, 方程个数就正好等于非终止状态数,既省了变量又天然表达了"到达即结束、不再贡献字符数"。
  • AC 自动机是"把无限长的历史压成有限状态"的标准工具。 只需要保留最长的 「某个模式串的前缀」后缀;终止标记沿 fail 链传播,是判定"已命中"的关键一步。
  • 模意义高斯消元:模数是质数,除法用费马小定理求逆元;主元列归一化后 回代只需一次减法与一次乘法,写起来最省心。

数据来源说明。 本题素材源目录带 data.py 分层数据生成器,data/ 的 10 个测试点 是自造数据(点 1–4 为边界/结构层,点 7–10 为顶格卡常层),题面则是按 「信息学奥赛一本通 · 高手训练篇」重建的,与官方原题可能存在细节偏差。 其中点 3 的 PP 是 1515 个单字母串,期望为有理数 26/1526/15,可顺便检验分数取模那一步。 素材源的 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)的约束、模数与本题完全一致, 可交叉印证解法。