无限链计数

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

把无限链看成禁止串 AC 自动机上的双无限路径,缩点成 DAG 后按「环 SCC 起、有限路径、环 SCC 收」数路径,遇多环或非简单环环节则判无穷。

OJ: roj

题目 ID: 1708

难度:提高+/省选-

标签:字符串AC自动机强连通分量拓扑排序python

创建: 2026-10-07 17:47

更新: 2026-10-07 17:47

形式化题目

字母表取前 tt 个小写字母,给定 nn 个禁止串 s1,s2,…,sns_1, s_2, \dots, s_n。 求双无限(两端都无限长)的字母序列 w ⁣:Z→Σw \colon \mathbb{Z} \to \Sigma 的数量,满足

  • 合法性:任意位置 ii 起的子串 w[i .. i+∣sk∣−1]w[i\,..\,i+|s_k|-1] 都不等于 sks_k(1⩽k⩽n1 \leqslant k \leqslant n);
  • 去重规则:两条链 A,BA, B 视为同一条当且仅当存在整数 kk 使 A[i+k]=B[i]A[i+k] = B[i] 对一切 ii 成立, 即二者互为平移。

输出满足条件的不同链数;若有无穷多条输出 −1-1。数据规模:t⩽6t \leqslant 6,n⩽1000n \leqslant 1000, 每个禁止串长度 ⩽10\leqslant 10,答案保证不超过 231−12^{31}-1。

题面给的第一个例子是 t=2t = 2、禁止串 {ab,ba}\{ab, ba\}:只有 …aaa……aaa… 与 …bbb……bbb… 两条。 第二个例子 t=2t = 2、禁止串 {ab}\{ab\} 有三条:…aaa……aaa…、…bbb……bbb… 与 …bbbbaaa……bbbbaaa… (前半段全是 b、后半段全是 a,交界处唯一的 ba 不含禁止串 ab)。

正解

思路

把链变成自动机上的路径。 先用 nn 个禁止串建 AC 自动机, 每个结点代表"已匹配的某个后缀",禁止结点是某个禁止串的结尾,或它的 fail 祖先里有禁止串结尾 (后者意味着走到这里就已经出现了禁止串)。一条合法链就是这台自动机上的一条路径, 只要结点与转移都不碰到禁止结点,就不会出现任何禁止串。

链是双无限的,所以对应的是一条双无限走法(两侧都无限长)。去掉禁止结点与射向它们的转移后, 得到一张有向图 GG(顶点数 ⩽10000+1\leqslant 10000 + 1,出度 ⩽t⩽6\leqslant t \leqslant 6,边数 ⩽60006\leqslant 60006)。

为什么要缩点。 图 GG 可以任意复杂,但把它按强连通分量(SCC)缩成一棵 DAG 后, 性质立刻变简单:拓扑序下每条转移的 SCC 编号只会单调不减。 而双无限走法两侧都无限长,拓扑序又只能前进不能后退,所以 一条走法只会用到有限多个 SCC——最左边的 SCC 向左无限延伸、最右边的 SCC 向右无限延伸, 中间夹的是一段有限的 DAG 路径。于是

一条双无限链  ⟺  一条「左端 SCC→有限 DAG 路径→右端 SCC」的路径. \text{一条双无限链} \;\Longleftrightarrow\; \text{一条「左端 SCC} \to \text{有限 DAG 路径} \to \text{右端 SCC」的路径}.

两端的 SCC 必须能提供"无限次走",也就是必须含环;中间的 SCC 只能提供有限的一段。

什么时候答案是 −1-1(无穷多)。 有两个独立的来源:

  1. 某个含环的 SCC 不是简单环。 在 kk 个顶点的 SCC 里,内部边数至少 kk; 恰好等于 kk 时它是一条简单环,从任一顶点出发的无限走法唯一; 一旦内部边数 >> 顶点数,同一段无限走法就有了至少两种走法(可以选不同的环、或绕不同圈数), 链的数量无穷。所以只要存在 inner > size 的 SCC,直接输出 −1-1。
  2. DAG 路径上有 ⩾3\geqslant 3 个环 SCC。 三个环中夹在中间的那个可以任意绕圈: 绕 mm 圈与绕 m+1m+1 圈得到的两条链不可能互为平移(平移保长度结构),所以链无穷。 因此路径上环 SCC 数达到 33 就输出 −1-1。

排除这两种情况后,中间夹着的 SCC 全部是无自环的单点,走法是唯一的; 两端的环 SCC 都是简单环,无限走法也是唯一的。所以一条「环 SCC →\to DAG 路径 →\to 环 SCC」 的路径恰好对应一条链,不重不漏。

路径计数。 在缩点 DAG 上做拓扑 DP:pathCnt[v] 表示"从某个环 SCC 出发、终点恰为 vv 的路径条数", cycleOnPath[v] 表示这些路径上环 SCC 个数的最大值(用于上面的 −1-1 判定)。 初始化时入度为 00 的 SCC 只能从自己出发;每个 SCC 出队时,若自己是环,就追加一条长度为 00 的路径; 再把计数沿边下传。注意缩点时要保留重边——两条平行边代表两种不同的转移,是不同的链, 所以下传时是"每条边各算一次"。最终答案是所有环 SCC 的 pathCnt 之和 (按"收尾的环 SCC"给链归类)。

用两个小例子核对。 第一个例子 t=2t = 2、禁止串 {ab}\{ab\}:结点 00(根,空后缀)、11(后缀 a), ab 的结尾是禁止结点。去掉禁止结点后剩下的转移是 0→b00 \xrightarrow{b} 0(自环)、0→a10 \xrightarrow{a} 1、 1→a11 \xrightarrow{a} 1(自环)。缩点得到两个都是简单环的 SCC,DAG 边为 0→10 \to 1,于是

收尾 SCC 路径 对应链
00 长度 00:00 自己绕自环 …bbb……bbb…
11 长度 00:11 自己绕自环 …aaa……aaa…
11 0→10 \to 1:先无限绕 00,再无限绕 11 …bbbbaaa……bbbbaaa…

三条,与题面一致。

第二个例子 t=2t = 2、禁止串 {ab,ba}\{ab, ba\}:两条双串都被禁,任意跨字母的相邻对都不合法, 剩下的只有 0→a00 \xrightarrow{a} 0 与 1→b11 \xrightarrow{b} 1 两个自环 SCC,且它们之间没有边, 所以只有 …aaa……aaa… 与 …bbb……bbb… 两条,同样与题面一致。

实现要点。 AC 自动机要用 BFS 把转移补齐成完整转移表(失配时该走到哪个状态), 并在 BFS 中把禁止标记沿 fail 链传递;Tarjan 求 SCC 时顺带统计每个 SCC 的顶点数与内部边数—— 内部边数的统计必须在原图上做(comp[u] == comp[v] 的边),跨 SCC 的边才建成 DAG。Python 版 Tarjan 写成显式栈的迭代版,避免链状自动机把递归压爆。

代码

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 17:47
# update_at: 2026-10-07 17:47

import sys
from collections import deque

type Graph = list[list[int]]  # 邻接表:graph[u] 是结点 u 的出边终点列表


def build_machine(t: int, pats: list[str]) -> tuple[list[list[int]], list[bool]]:
    """建禁止串的 AC 自动机,返回补齐后的转移表和「禁止」标记(已沿 fail 链传递)。"""
    nxt = [[0] * t]
    banned = [False]
    for pat in pats:
        u = 0
        for ch in pat:
            c = ord(ch) - 97
            if nxt[u][c] == 0:
                nxt[u][c] = len(nxt)
                nxt.append([0] * t)
                banned.append(False)
            u = nxt[u][c]
        banned[u] = True

    fail = [0] * len(nxt)
    que = deque(c for c in nxt[0] if c)  # 根的直接儿子(0 表示根本没有这个儿子)
    while que:
        u = que.popleft()
        banned[u] = banned[u] or banned[fail[u]]  # 禁止标记沿 fail 链下传
        row = nxt[u]
        for c in range(t):
            if row[c]:
                fail[row[c]] = nxt[fail[u]][c]
                que.append(row[c])
            else:
                row[c] = nxt[fail[u]][c]  # 补齐转移:失配后该走到哪
    return nxt, banned


def strong_components(graph: Graph) -> list[int]:
    """Tarjan 求强连通分量(迭代版,避免深递归),返回每个结点所属的 SCC 编号。"""
    m = len(graph)
    dfn = [-1] * m  # -1 表示还没访问过
    low = [0] * m
    comp = [-1] * m
    on_stack = [False] * m
    stack: list[int] = []  # Tarjan 栈
    clock = 0
    comp_cnt = 0

    for root in range(m):
        if dfn[root] >= 0:
            continue
        work = [(root, 0)]  # (结点, 下一条要看的出边下标)
        while work:
            u, i = work[-1]
            if i == 0:
                dfn[u] = low[u] = clock
                clock += 1
                stack.append(u)
                on_stack[u] = True
            if i < len(graph[u]):
                work[-1] = (u, i + 1)
                v = graph[u][i]
                if dfn[v] < 0:
                    work.append((v, 0))
                elif on_stack[v]:
                    low[u] = min(low[u], dfn[v])
            else:
                work.pop()
                if low[u] == dfn[u]:  # u 是这个 SCC 里第一个被访问的结点
                    while True:
                        w = stack.pop()
                        on_stack[w] = False
                        comp[w] = comp_cnt
                        if w == u:
                            break
                    comp_cnt += 1
                if work:
                    p = work[-1][0]
                    low[p] = min(low[p], low[u])
    return comp


def count_chains(t: int, pats: list[str]) -> int:
    """统计两端都无限、平移视为同一条的合法链数量;有无穷多条时返回 -1。"""
    nxt, banned = build_machine(t, pats)
    # 只有「非禁止结点 + 非禁止转移」上的双无限路径才是合法链
    graph: Graph = [
        [v for v in nxt[u] if not banned[v]] if not banned[u] else [] for u in range(len(nxt))
    ]
    comp = strong_components(graph)
    size = [0] * (max(comp) + 1)  # 每个 SCC 的结点数
    inner = [0] * (max(comp) + 1)  # 每个 SCC 的内部边数
    for u in range(len(nxt)):
        if banned[u]:
            continue
        size[comp[u]] += 1
        inner[comp[u]] += sum(1 for v in graph[u] if comp[v] == comp[u])

    # SCC 是简单环 ⟺ 内部边数等于结点数;多出来的边意味着这个 SCC 自己就能造出无穷多条链
    if any(inner[c] > size[c] for c in range(len(size))):
        return -1
    is_cycle = [size[c] > 0 and inner[c] == size[c] for c in range(len(size))]

    out: Graph = [[] for _ in size]
    indeg = [0] * len(size)
    for u in range(len(nxt)):
        if banned[u]:
            continue
        for v in graph[u]:
            if comp[u] != comp[v]:
                out[comp[u]].append(comp[v])  # 缩点 DAG 保留重边:不同转移是不同的链
                indeg[comp[v]] += 1

    # 链 = 「环 SCC 起 + DAG 有限路径 + 环 SCC 收」,按拓扑序数路径
    path_cnt = [0] * len(size)  # 从某个环 SCC 出发、终点是这个 SCC 的路径条数
    cycle_on_path = [0] * len(size)  # 这些路径上环 SCC 个数的最大值
    que = deque(c for c in range(len(size)) if indeg[c] == 0)
    for c in que:
        cycle_on_path[c] = 1 if is_cycle[c] else 0  # 路径可以就从自己这个环开始
    while que:
        u = que.popleft()
        if cycle_on_path[u] >= 3:  # 夹在中间的环 SCC 能绕任意圈:无穷多条
            return -1
        if is_cycle[u]:
            path_cnt[u] += 1  # 长度 0 的路径:自己就是一个环
        for v in out[u]:
            path_cnt[v] += path_cnt[u]
            cycle_on_path[v] = max(cycle_on_path[v], cycle_on_path[u] + (1 if is_cycle[v] else 0))
            indeg[v] -= 1
            if indeg[v] == 0:
                que.append(v)
    return sum(path_cnt[c] for c in range(len(size)) if is_cycle[c])


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().split())
    t = int(next(tokens))
    n = int(next(tokens))
    pats = [next(tokens).decode() for _ in range(n)]
    print(count_chains(t, pats))


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 17:47
 * update_at: 2026-10-07 17:47
 */

// 1708 无限链计数
// 一条双无限链(左右都能平移,平移后视为同一条)就是禁止串 AC 自动机上的
// 一条双无限转移路径;把非终止结点、非终止转移缩成 SCC 之后,路径的 SCC
// 序列在缩点 DAG 上单调,所以每条链恰好对应「环 SCC 出发 + DAG 有限路径 +
// 环 SCC 收尾」这样一条 DAG 路径:
//   * SCC 内部边数 > 结点数 ⟺ 这个 SCC 不是简单环 ⟺ 链有无穷多条(-1);
//   * DAG 路径上夹在中间的环 SCC 还能随便绕圈,所以路径上环 SCC 数 ≥ 3 时
//     也有无穷多条(-1);
//   * 否则答案就是「环 SCC 到环 SCC」的 DAG 路径条数。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXNODE = 10005;  // 禁止串总长 ≤ 1000 × 10 = 10000,结点数 ≤ 10001
const int MAXE = 60005;     // 每个非终止结点至多 t ≤ 6 条非终止转移

int t, n;                   // t:字母表大小;n:禁止串个数
int trie[MAXNODE][6];       // AC 自动机的完整转移(fail 指针补齐之后)
int failLink[MAXNODE];      // 失配指针
bool terminal[MAXNODE];     // 该结点或它的某个 fail 祖先是禁止串的结尾
int nodeCnt;                // 结点个数,根固定为 0

// 一张图的链式前向星:g1 是「非终止结点 + 非终止转移」的原图,
// g2 是缩点后的 DAG(保留重边,重边代表不同的转移,必须分别计数)
struct Edge {
    int to;
    int next;
};
Edge g1[MAXE];
Edge g2[MAXE];
int head1[MAXNODE], head2[MAXNODE];
int cnt1, cnt2;

void add_edge1(int u, int v) {
    cnt1++;
    g1[cnt1].to = v;
    g1[cnt1].next = head1[u];
    head1[u] = cnt1;
}

void add_edge2(int u, int v) {
    cnt2++;
    g2[cnt2].to = v;
    g2[cnt2].next = head2[u];
    head2[u] = cnt2;
}

// 把一个禁止串插入 Trie
void insert_word(const char *s) {
    int u = 0;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        if (trie[u][c] == 0) trie[u][c] = ++nodeCnt;
        u = trie[u][c];
    }
    terminal[u] = true;
}

// 建 fail 指针,同时把转移补齐成「走到哪个状态」的完整转移表,
// 并把禁止标记沿 fail 链传递到每个结点
void build_fail() {
    queue<int> que;
    for (int c = 0; c < t; c++)
        if (trie[0][c]) que.push(trie[0][c]);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        terminal[u] = terminal[u] || terminal[failLink[u]];  // fail 链传递
        for (int c = 0; c < t; c++) {
            if (trie[u][c]) {
                failLink[trie[u][c]] = trie[failLink[u]][c];
                que.push(trie[u][c]);
            } else {
                trie[u][c] = trie[failLink[u]][c];
            }
        }
    }
}

int dfn[MAXNODE], low[MAXNODE], timerClock;
int stk[MAXNODE], top;
bool inStack[MAXNODE];
int sccId[MAXNODE], sccCnt;
int sccNode[MAXNODE];      // 每个 SCC 的结点数
int sccInner[MAXNODE];     // 每个 SCC 的内部边数
bool isCycleScc[MAXNODE];  // 内部边数 == 结点数 ⟺ 这个 SCC 就是一个简单环

// Tarjan 求强连通分量(只跑原图上非终止的结点)
void tarjan(int u) {
    dfn[u] = low[u] = ++timerClock;
    stk[++top] = u;
    inStack[u] = true;
    for (int e = head1[u]; e; e = g1[e].next) {
        int v = g1[e].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        sccCnt++;
        int k;
        do {
            k = stk[top--];
            inStack[k] = false;
            sccId[k] = sccCnt;
            sccNode[sccCnt]++;
        } while (k != u);
    }
}

int indeg[MAXNODE];  // 缩点 DAG 上每个 SCC 的入度,用来做 Kahn 拓扑排序
ll pathCnt[MAXNODE]; // pathCnt[v]:从某个环 SCC 出发、终点是 v 的 DAG 路径条数
int cycleOnPath[MAXNODE]; // cycleOnPath[v]:这些路径上环 SCC 个数的最大值

int main() {
    scanf("%d %d", &t, &n);
    char s[15];
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        insert_word(s);
    }
    build_fail();

    // 建原图:结点和转移都不能碰到禁止串
    for (int u = 0; u <= nodeCnt; u++) {
        if (terminal[u]) continue;
        for (int c = 0; c < t; c++) {
            int v = trie[u][c];
            if (terminal[v]) continue;
            add_edge1(u, v);
        }
    }
    for (int u = 0; u <= nodeCnt; u++)
        if (!terminal[u] && !dfn[u]) tarjan(u);

    // 缩点:统计 SCC 内部边数,跨 SCC 的边建成 DAG
    for (int u = 0; u <= nodeCnt; u++) {
        if (terminal[u]) continue;
        for (int e = head1[u]; e; e = g1[e].next) {
            int v = g1[e].to;
            if (sccId[u] == sccId[v]) {
                sccInner[sccId[u]]++;
            } else {
                add_edge2(sccId[u], sccId[v]);
                indeg[sccId[v]]++;
            }
        }
    }
    for (int i = 1; i <= sccCnt; i++) {
        if (sccInner[i] > sccNode[i]) {  // 不是简单环:同一个 SCC 里就有无穷多条链
            printf("-1\n");
            return 0;
        }
        if (sccInner[i] == sccNode[i]) isCycleScc[i] = true;
    }

    // 缩点 DAG 上按拓扑序做路径计数
    queue<int> que;
    for (int i = 1; i <= sccCnt; i++) {
        if (indeg[i] == 0) {
            que.push(i);
            cycleOnPath[i] = isCycleScc[i] ? 1 : 0;  // 路径可以就从自己这个环开始
        }
    }
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        if (cycleOnPath[u] >= 3) {  // 中间的环 SCC 可以绕任意圈:无穷多
            printf("-1\n");
            return 0;
        }
        if (isCycleScc[u]) pathCnt[u]++;  // 长度 0 的路径:自己就是一个环
        for (int e = head2[u]; e; e = g2[e].next) {
            int v = g2[e].to;
            pathCnt[v] += pathCnt[u];
            cycleOnPath[v] = max(cycleOnPath[v], cycleOnPath[u] + (isCycleScc[v] ? 1 : 0));
            if (--indeg[v] == 0) que.push(v);
        }
    }

    ll answer = 0;
    for (int i = 1; i <= sccCnt; i++)
        if (isCycleScc[i]) answer += pathCnt[i];  // 每条链以收尾的环 SCC 归类,不重不漏
    printf("%lld\n", answer);
    return 0;
}

复杂度

  • 时间:建 AC 自动机 O(∑∣si∣⋅t)O(\sum |s_i| \cdot t);建图 O(Vt)O(V t);Tarjan 与缩点 O(V+E)O(V + E); 缩点 DAG 上拓扑 DP O(V+E)O(V + E)。顶点数 V⩽1+1000×10=10001V \leqslant 1 + 1000 \times 10 = 10001, 边数 E⩽Vt⩽60006E \leqslant V t \leqslant 60006。故总时间 O(∑∣si∣⋅t+Vt)O(\sum |s_i| \cdot t + V t),与 ∑∣si∣\sum|s_i| 线性。 实测 10 个数据点中最大者(t=6t = 6、n=1000n = 1000、串长 1010)CPython 约 0.020.02 s, C++ 版本在 O2O2 下更快,远低于 3000 ms 限时。
  • 空间:AC 自动机转移表 O(Vt)O(V t),图与 Tarjan 辅助数组 O(V+E)O(V + E), 合计约 O(Vt)O(V t);C++ 用全局静态数组(MAXNODE = 10005、MAXE = 60005), 峰值内存远低于 256 MB。Python 的邻接表形式在顶格数据下也只有几 MB。
  • 与 main.cpp 的关系:两者是同算法同复杂度,main.cpp 用链式前向星 + 显式队列 + 递归 Tarjan, main.py 用邻接表 + 迭代 Tarjan,输出完全一致(10/10 逐字节相同)。 本题不存在 Python 特有的 TLE 风险。

总结

  • 先去禁止串,再谈计数:AC 自动机把"不含禁止串"变成"路径不碰禁止结点", 多串匹配问题随之转成一张图上的路径问题。
  • 双无限 + 缩点 = 有限长度的 DAG 路径:拓扑序不能后退,所以两侧无限的走法只能 用有限多个 SCC,链的结构被压缩成"环 SCC + DAG 有限路径 + 环 SCC"三段。
  • 无穷多有两个来源,且彼此独立:SCC 内部边数超过顶点数(不是简单环), 或 DAG 路径上环 SCC 个数 ⩾3\geqslant 3(中间的环可以随便绕)。二者都直接输出 −1-1。
  • 缩点必须保留重边:平行的两条转移是不同的链,删重边会漏计数。
  • 路径计数按收尾 SCC 归类:以"终点所在的环 SCC"给链分类,sum(pathCnt[环 SCC]) 不重不漏。
  • 注:本题素材源目录里带有 data.py,随仓 data/ 是按题面范围(t⩽6t \leqslant 6、n⩽1000n \leqslant 1000、 串长 ⩽10\leqslant 10)自行构造的分层数据;题面本身是网络重建的版本, 文字表述以仓库内 content.md(即 problem.md)为准。