DNA序列

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

禁止子串建 AC 自动机得到 DFA,删掉危险状态后在安全状态间建重数转移矩阵,矩阵快速幂求长度 n 的合法串数。

OJ: roj

题目 ID: 1705

难度:提高+/省选-

标签:AC自动机矩阵快速幂字符串python

创建: 2026-10-07 16:05

更新: 2026-10-07 16:05

形式化题目

字母表 Σ={A,C,T,G}\Sigma = \{\texttt{A}, \texttt{C}, \texttt{T}, \texttt{G}\},∣Σ∣=4|\Sigma| = 4。给定 mm 个禁止串 s1,…,sms_1, \dots, s_m(每个长度不超过 1010),求长度为 nn 的串 w∈Σnw \in \Sigma^n 的个数,使得 ww 的任意连续子串都不等于某个 sis_i,答案对 100000100000 取模。

与原题样例一致:n=3n = 3,禁止串为 AT、AC、AG、AA 时,位置 11 与位置 22 都不能是 A(否则以 A 开头的两位子串必然命中),位置 33 不受限,答案为 3×3×4=363 \times 3 \times 4 = 36。

数据范围:n⩽2×109n \leqslant 2 \times 10^9,m⩽10m \leqslant 10,∣si∣⩽10|s_i| \leqslant 10。 nn 大到无法逐位递推,但串长与 mm 都很小,自动机状态数不超过 1+10×10=1011 + 10 \times 10 = 101。

正解

思路

先想一个能算的小数据做法。 从左往右逐位填字符,每一步只需保证"当前文本的某个后缀不是禁止串"。 把"文本后缀与禁止串前缀的匹配情况"抽成一个状态,设 ft(u)f_t(u) 表示填了 tt 位后状态为 uu 的方案数,则

ft+1(v)=∑uft(u)⋅#{ c∈Σ:u→  c  v, v 安全 }. f_{t+1}(v) = \sum_{u} f_t(u) \cdot \#\{\,c \in \Sigma : u \xrightarrow{\;c\;} v,\ v \text{ 安全}\,\}.

nn 小时按 tt 递推 nn 轮即可,但 nn 到 2×1092 \times 10^9。注意这个递推式与 tt 无关: 它就是把同一个矩阵连续作用 nn 次,于是可以用矩阵快速幂把 nn 消成 log⁡n\log n。

下面三件事:后缀状态怎么来、递推矩阵怎么建、终点的边界怎么算。

第一步:AC 自动机把"后缀检查"变成走一条状态边。 把所有禁止串建成 Trie, 每个节点代表"某个禁止串的一个前缀"。补上 fail 指针与缺失边之后得到确定的 DFA:

  • 状态 uu:已填文本的最长后缀恰好落在 Trie 的哪个节点上;
  • 转移 u→cvu \xrightarrow{c} v:再填一个字符 cc,新文本的后缀对应的状态变成 vv;
  • 危险标记 danger:节点 uu 或它的任意 fail 祖先是某个 sis_i 的结尾。

danger 必须沿 fail 链传递。走到 uu 意味着文本的某个后缀就是"根到 uu 的这条路径"; 如果这条路径的某个后缀本身又是一个完整禁止串(对应某个 fail 祖先为结尾节点), 那么文本同样已经非法。漏掉这一步就会把 XAT 这类文本误判为合法。 把缺失边补成 nxt[u][c] = nxt[fail[u]][c] 后,u→cvu \xrightarrow{c} v 只需一次数组查询。

第二步:删掉危险状态,在安全状态之间建重数矩阵。 一个状态 danger 为真, 说明此刻文本已经含有完整禁止串,再往后填什么都救不回来,直接从图中删掉。 剩下的状态称为安全状态,记个数为 KK(K⩽101K \leqslant 101),构造 K×KK \times K 的转移矩阵

Mi,j=#{ c∈Σ:ui→cuj, uj 安全 }. M_{i,j} = \#\{\,c \in \Sigma : u_i \xrightarrow{c} u_j,\ u_j \text{ 安全}\,\}.

Mi,jM_{i,j} 是重数而不是 0/10/1:多个字符可能落到同一个状态,它们对应不同的串,必须都算进去。 Mi,jM_{i,j} 还可以大于 11 的另一个来源是 DFA 补边后同一落点被多条字符边命中。

第三步:答案是 (Mn)0,∗(M^n)_{0,*} 的和。 起点为状态 00(空文本,落在根)。 一条长度 nn 的路径对应一个长度为 nn 的串,且路径上每个状态都安全 ⟺ 该串的每个前缀的 所有后缀都不是禁止串 ⟺ 该串不含禁止串作为子串。于是

ans=∑j=0K−1(Mn)0, j, \text{ans} = \sum_{j=0}^{K-1} (M^n)_{0,\,j},

用倍增法求 MnM^n:nn 的二进制最多 3131 位,每次平方一次 O(K3)O(K^3) 乘法, 总复杂度 O(K3log⁡n)O(K^3 \log n)。

用样例核对一遍。 禁止串是 AT、AC、AG、AA,它们都是长度 22,所以 Trie 只有 两个非根节点:A 与 A 的四条儿子。关键在于节点 A 本身不是任何禁止串的结尾 (禁止串都是两位),它安全;A 的四个儿子才是结尾节点,全部 danger。删掉危险节点后剩下 两个安全状态:根与 A。转移是

  • 根走 C/T/G 都回根(共 33 条边),根走 A 到状态 A(11 条边);
  • 状态 A 的四个字符边都落到危险节点,被删掉,所以这一行全 00。
M=(3100),Mn=(3n3n−100), M = \begin{pmatrix} 3 & 1 \\ 0 & 0 \end{pmatrix},\qquad M^n = \begin{pmatrix} 3^n & 3^{n-1} \\ 0 & 0 \end{pmatrix},

第 00 行之和为 3n+3n−1=4⋅3 n−13^n + 3^{n-1} = 4 \cdot 3^{\,n-1}。n=3n = 3 时得到 27+9=3627 + 9 = 36,与样例一致。 两项的含义正好对应样例的手算:3n−13^{n-1} 是"最后一位取 A"(倒数第二位起必须合法), 3n3^n 是"最后一位取 C/T/G"。这也说明不需要为最后一位做特殊处理, 只要把 A 这样的合法前缀保留为安全状态,矩阵幂自动把结尾的各种情形都数进去了。

关于素材源。 本题与经典题 POJ 2778 DNA Sequence 完全同型(m⩽10m \leqslant 10、 n⩽2×109n \leqslant 2 \times 10^9、串长 ⩽10\leqslant 10、字母表 ACTG、模 100000100000), new_ROJ 中的 std.cpp 就是这一算法。已实测它在全部 10 个测试点上与数据一致, 因此本题按其思路独立重写,不照抄。

代码

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 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++ 版(同一算法):

cpp
/**
 * 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 自动机 O ⁣(∣Σ∣∑∣si∣)O\!\left(|\Sigma| \sum |s_i|\right);矩阵快速幂 O(K3log⁡n)O(K^3 \log n), 其中 K⩽101K \leqslant 101、log⁡2n⩽31\log_2 n \leqslant 31。实测最大点(n=2×109n = 2 \times 10^9) C++ 约 0.03 s,限时 1000 ms。
  • 空间:转移矩阵 O(K2)O(K^2),K⩽101K \leqslant 101 时远小于 1 MB,限时 64 MB。
  • Python 侧:矩阵乘法把 yy 的每一行压成一个大整数,一次整数乘法就得到结果的一整行, 把 O(K3)O(K^3) 次小整数乘加换成 O(K2)O(K^2) 次大整数乘法,Python 下 10 个点全部在 1 s 内跑完。

总结

  • 子串约束 ⟺ 自动机上的路径约束:禁止"含某个模式作为子串",等价于在 AC 自动机的 DFA 上 永不经过带终止标记的状态;danger 沿 fail 链继承这一步不能省。
  • 与 tt 无关的递推 ⟺ 矩阵幂:ft+1=Mftf_{t+1} = M f_t 中 MM 恒定,n=109n = 10^9 也只是 log⁡n\log n 次矩阵乘法。
  • 转移矩阵记重数不记布尔值:多个字符落到同一状态要累加,否则会少数。
  • 合法前缀要保留:A 这类"是禁止串前缀但不是禁止串本身"的状态必须留下, 它让"结尾恰好把串带向危险"的情形被正确计数,不必单独处理最后一位。
  • 模型识别:本题与 POJ 2778 同型,属于 AC 自动机 + 矩阵快速幂的标准套路; 识别出模型后,n⩽2×109n \leqslant 2 \times 10^9 这个异常大的范围就是最强的提示。