量子纠缠

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

把串看成 trie 状态,纠缠即 Myhill-Nerode 右语言等价,用并查集合并状态并沿 10 条出边做同余闭包,查询时每步跳到代表元。

OJ: roj

题目 ID: 1703

难度:提高+/省选-

标签:字符串trie并查集自动机python

创建: 2026-10-07 17:19

更新: 2026-10-07 17:19

形式化题目

维护一个只增不减的数字串(字符集 Σ={0,…,9}\Sigma = \{0, \dots, 9\})集合 SS,初始 S=∅S = \varnothing。 依次处理 mm 条操作,每条是以下三种之一:

  • 1 s:把串 ss 加入 SS;
  • 2 s:询问 s∈Ss \in S 与否,输出 11 / 00;
  • 3 a b:令 aa 与 bb 互相纠缠。

"纠缠"是一个双向的后缀等价约束:对任意 C,D∈Σ∗C, D \in \Sigma^{*}(可为空串),

a+C∈S  ⟺  b+C∈S,b+D∈S  ⟺  a+D∈S. a + C \in S \iff b + C \in S, \qquad b + D \in S \iff a + D \in S .

两条其实互为同一命题的两半,合起来就是:对任意后缀 XX,

  a+X∈S  ⟺  b+X∈S   \boxed{\;a + X \in S \iff b + X \in S\;}

因此一次 3 操作会把满足该式的一切串立即纳入 SS——可能有无穷多个, 如把 aa 与 a+da+d 纠缠后,a+dka + d^{k}(k⩾1k \geqslant 1)全部从"从未直接加入"变成"必答 11"。 题面还强调:纠缠是一种持续状态,纠缠之后的任何 1 操作同样可能连带引入无穷多个串。

约束:m⩽105m \leqslant 10^{5},c⩽2050c \leqslant 2050(cc 为 1 与 3 操作次数之和), Slen⩽8×106S_{\text{len}} \leqslant 8 \times 10^{6}(所有 2 操作询问串的总长度),L⩽50L \leqslant 50 (1 / 3 操作中数字串的长度上限)。

正解

思路

关键一步:把"集合"换成"状态"。 先看一个纯暴力:维护串的集合 set\text{set}, 1 直接插入,2 直接查找。它对 3 无能为力——一次纠缠要枚举并插入无穷多个串。

突破口在于看清纠缠的定义式:a+X∈S  ⟺  b+X∈Sa + X \in S \iff b + X \in S 对一切后缀 XX 成立。 这正是自动机理论里 Myhill–Nerode 的右语言等价 ≡S\equiv_S:

a≡Sb  ⟺  { X:a+X∈S }={ X:b+X∈S }. a \equiv_S b \iff \{\,X : a + X \in S\,\} = \{\,X : b + X \in S\,\}.

于是"s∈Ss \in S"不再依附于具体的串 ss,而可以挂到它的等价类上: 只要 ss 的等价类被标记为"进集合",ss 就答 11。而 3 a b 这条操作, 用这个视角看就是一句朴素得多的指令:

把 aa 与 bb 归入同一个等价类。

但等价类不能随便并——要对出边取闭包。 设状态 uu、vv 同类。对任意字符 cc 和后缀 XX,

ucX∈S  ⟺  u+(cX)∈S  ⟺  v+(cX)∈S  ⟺  vcX∈S, u c X \in S \iff u + (cX) \in S \iff v + (cX) \in S \iff v c X \in S,

所以 ucu c 与 vcv c 也必须同类(同一条推导里,XX 取遍所有串)。这意味着合并 u,vu, v 时必须顺带合并 ucu c、vcv c 两层状态对;而这些后继的合并又会引出新的对, 所以要用一个显式栈把闭包做到底,直到没有新的状态对为止。

数据结构落地。 把每个串看成 trie 上的一个节点(根 = 空串,节点 uu 走字符 cc 到的 节点记 u.cu.c)。1 操作 = 把 ss 末节点的等价类打上标记 fin\text{fin};2 操作 = 沿 ss 走到末节点,看它所在类的 fin\text{fin};3 操作 = 合并两个末节点所在的类。

等价类用并查集维护,fa[u] 指向同类里的另一个节点。合并时把 uu 的 10 条出边与 vv 的 对应出边逐条对齐:

merge(u,v):若 u.c=0 而 v.c≠0  ⇒  u.c←v.c;若两者都非 0  ⇒  递归合并 (u.c,  v.c). \text{merge}(u, v):\quad \text{若 } u.c = 0 \text{ 而 } v.c \neq 0 \;\Rightarrow\; u.c \leftarrow v.c; \qquad \text{若两者都非 } 0 \;\Rightarrow\; \text{递归合并 } (u.c,\; v.c).

出边表始终挂在代表元上,并且两类合并时把被合并者已有的出边"接"到代表元上—— 这样后面到达的串,哪怕前缀路径是"晚"才走出来的,也会自动共享整个类已积累的出边。

查询时必须每步跳代表元。 走 ss 的每一步都要 find_root:因为 ss 的前缀节点 可能在之后的 3 操作里被并进别的类,直接读 ch[cur][c] 会读到陈旧的代表元。 这正是本题最容易写错的地方——等价类是动态的,trie 的父子关系不能静态看待。

"集合只增不减"的红利。 fin 只置真、不置假;等价类只合并、不拆分。 所以每一个被加入或被纠缠"传染"到的串,此后永远答 11, fin[a]=fin[a]∨fin[b]\texttt{fin}[a] = \texttt{fin}[a] \lor \texttt{fin}[b] 一行就够了,不需要任何撤销逻辑。

用题面样例追踪一遍:3 12 13 让状态 12 与 13 同类,于是在它们的出边闭包里 12 走 4 得到的 124 与 13 走 4 得到的 134 也同类;此后 1 124 把 124 的类打上标记,2 134 自然答 11——从未直接加入过的 134 被连带进集合, 这就是纠缠"传染"的最小实例。

代码

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

import sys

ROOT = 1  # 根状态(空串)的编号;状态 0 是"这条出边不存在"的哨兵

ch: list[list[int]] = [[0] * 10, [0] * 10]  # ch[u][c]:状态 u 走字符 c 到哪个状态
fa: list[int] = [0, 1]                      # 并查集父指针,代表元满足 fa[u] == u
fin: list[bool] = [False, False]            # 该状态所在等价类是否已进信息集


def find_root(x: int) -> int:
    """并查集找代表元,顺路把路径上的点都挂到根上。"""
    r = x
    while fa[r] != r:
        r = fa[r]
    while fa[x] != r:
        fa[x], x = r, fa[x]
    return r


def ensure_state(s: bytes) -> int:
    """沿串 s 走自动机(缺的边现场开点),返回末状态所在等价类的代表元。"""
    cur = ROOT
    for d in s:
        c = d - 48
        if ch[cur][c] == 0:
            # 开点:ch / fa / fin 三个数组同步长一位,新状态自成一类
            ch.append([0] * 10)
            fa.append(len(fa))
            fin.append(False)
            ch[cur][c] = len(fa) - 1
        cur = find_root(ch[cur][c])
    return cur


def find_state(s: bytes) -> int:
    """询问串 s 落在哪个等价类;中途缺边说明 s 不在信息集,返回哨兵 0。"""
    cur = ROOT
    for d in s:
        c = d - 48
        nxt = ch[cur][c]
        if nxt == 0:
            return 0
        cur = find_root(nxt)
    return cur


def merge_state(p: int, q: int) -> None:
    """把 p、q 所在等价类并成一类,并对 10 条出边做同余闭包。

    纠缠要求两个状态右语言相同,所以同类状态对每个字符的后继也必须同类;
    后继合并又会引出新的状态对,用显式栈把闭包做到底(不递归,免爆栈)。
    """
    stack = [(p, q)]
    while stack:
        x, y = stack.pop()
        a, b = find_root(x), find_root(y)
        if a == b:  # 已经在同一类里
            continue
        fa[b] = a                                        # b 并入 a 的类
        fin[a] = fin[a] or fin[b]                        # 标记只置真不置假
        for c in range(10):
            u, v = ch[a][c], ch[b][c]
            if v == 0:                                   # b 这条出边是空的
                continue
            if u == 0:
                ch[a][c] = v                             # a 缺的边直接接上 b 的
                continue
            need_merge = find_root(u) != find_root(v)     # 两条后继还不在同一类
            if need_merge:
                stack.append((u, v))


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    m = int(next(data))
    out: list[str] = []
    added = False  # 是否出现过操作 1;一次都没加过串时信息集恒空
    for _ in range(m):
        op = next(data)
        if op == b'1':
            fin[ensure_state(next(data))] = True
            added = True
        elif op == b'2':
            s = next(data)
            v = find_state(s) if added else 0  # 空集直接答 0,省一趟自动机
            out.append('1' if v and fin[v] else '0')
        else:
            merge_state(ensure_state(next(data)), ensure_state(next(data)))
    # 答案先攒进列表再一次写出,避免 10^5 次 print 的开销;末尾补换行收尾
    if out:
        sys.stdout.write('\n'.join(out) + '\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 17:19
 * update_at: 2026-10-07 17:19
 */
// 一本通 1703《量子纠缠》:trie 上的状态等价类合并(并查集 + 出边同余闭包)。
//
// 建模:把每个数字串看作 trie 上的一个状态,"串在信息集中"记在该状态上的 fin 标记。
//   "纠缠 a b" 要求对任意后缀 X 都有 (a+X 在信息集) <=> (b+X 在信息集),
//   这正是 Myhill-Nerode 意义下"状态 a 与状态 b 右语言相同",两个状态必须并成一类。
// 合并两个等价类时,相同字符的出边也要成对合并,否则等价类不自洽;
// 而这些后继的等价类又可能被进一步合并,所以要用显式栈把闭包做到底。
// 出边只增不减地记在等价类代表元上,查询时每走一步先转到代表元,
// 于是同一类的所有串共享同一套后继 —— 晚到的 1 操作会自动"传染"整个类。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 状态数上界:操作 1 每条串 <= L 个点,操作 3 贡献两条串,故
// 点数 <= 1 + c*2*L = 1 + 2050*2*50 = 205001,这里取 25 万留余量
const int MAXNODE = 250005;
const int CHAR_SET = 10;     // 数字串的字符集 0~9

// 状态:出边表 + 并查集父指针 + 是否在信息集中的标记
struct Node {
    int ch[CHAR_SET];  // ch[c] = 走字符 c 到达的状态编号,0 表示没有这条出边
    int fa;            // 并查集父指针:指向同等价类的另一个状态
    bool fin;          // 该状态(等价类代表元)是否已经在信息集中
};

Node node[MAXNODE];  // node[u] 就是状态 u,状态 0 是"无出边"哨兵,根状态是 1
int node_cnt = 1;    // 已创建的状态个数(根状态编号为 1)
bool has_added;      // 是否发生过操作 1:fin 只置真不置假,没加过串时询问一律为 0

// 开一个新状态:出边全空,自己是独立等价类的代表元
int new_node() {
    node_cnt++;
    node[node_cnt].fa = node_cnt;
    node[node_cnt].fin = false;
    return node_cnt;
}

// 并查集找根 + 路径压缩,返回状态 x 所在等价类的代表元
int find_root(int x) {
    int r = x;
    while (node[r].fa != r) r = node[r].fa;  // 第一遍:找到根
    while (node[x].fa != x) {                // 第二遍:把路径上的点直接挂到根
        int p = node[x].fa;
        node[x].fa = r;
        x = p;
    }
    return r;
}

// 沿串 s 在自动机上走一遍,缺的边现场开点,返回末状态所在等价类的代表元
int ensure_state(const string& s) {
    int cur = 1;  // 根状态(空串)
    ll n = s.size();
    for (ll i = 0; i < n; i++) {
        int c = s[i] - '0';
        if (node[cur].ch[c] == 0) node[cur].ch[c] = new_node();
        cur = find_root(node[cur].ch[c]);
    }
    return cur;
}

// 询问串 s 落在哪个等价类:走不通返回 0,否则返回代表元
int find_state(const string& s) {
    int cur = 1;
    ll n = s.size();
    for (ll i = 0; i < n; i++) {
        int c = s[i] - '0';
        int nxt = node[cur].ch[c];
        if (nxt == 0) return 0;  // 前缀就不在 trie 里,串必然不在信息集中
        cur = find_root(nxt);
    }
    return cur;
}

// 合并 p、q 所在的两个等价类,并沿 10 条出边做同余闭包(显式栈代替递归)
void merge_state(int p, int q) {
    vector<pair<int, int> > stk;  // 待合并的状态对
    stk.push_back(make_pair(p, q));
    while (!stk.empty()) {
        int x = stk.back().first;
        int y = stk.back().second;
        stk.pop_back();
        int a = find_root(x);
        int b = find_root(y);
        if (a == b) continue;  // 已经在同一类里
        node[b].fa = a;        // b 并入 a 的等价类
        node[a].fin = node[a].fin || node[b].fin;
        for (int c = 0; c < CHAR_SET; c++) {
            int u = node[a].ch[c];
            int v = node[b].ch[c];
            if (v == 0) continue;  // b 这条出边是空的,没有要合并的后继
            if (u == 0) {
                node[a].ch[c] = v;  // a 缺的边直接接上 b 的
            } else if (find_root(u) != find_root(v)) {
                stk.push_back(make_pair(u, v));  // 两个后继也要同余
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    node[1].fa = 1;  // 根状态自己是代表元

    ll m;
    cin >> m;
    string s, a, b;
    for (ll i = 1; i <= m; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            cin >> s;  // 加入信息集的串
            node[ensure_state(s)].fin = true;
            has_added = true;
        } else if (op == 2) {
            cin >> s;  // 询问串
            // 一次 1 操作都没发生时信息集恒空,不必走自动机
            int v = has_added ? find_state(s) : 0;
            if (v != 0 && node[v].fin) {
                cout << 1 << '\n';
            } else {
                cout << 0 << '\n';
            }
        } else {
            cin >> a >> b;  // 互相纠缠的两个串
            merge_state(ensure_state(a), ensure_state(b));
        }
    }
    return 0;
}

复杂度

  • 时空规模由 cc 决定,与询问串长度无关:trie 只在 1 / 3 操作中开点, 1 贡献 11 条串、3 贡献 22 条串,每条串至多 LL 个新节点,故 ∣V∣⩽1+2cL≈2.05×105|V| \leqslant 1 + 2cL \approx 2.05 \times 10^{5}(本仓库数据里最多的是 problem7,∣V∣=66323|V| = 66323)。
  • 时间:1 / 2 操作各为 O(∣s∣)O(|s|);3 操作的闭包代价可以用 "出边被搬运的总次数"来摊还——每条出边一旦被搬进某个代表元并永久留在那里, 且被合并的等价类不会再拆开,故闭包总代价为 O(∣V∣⋅∣Σ∣⋅α)O(|V| \cdot |\Sigma| \cdot \alpha)。 总计 O(m+∣V∣⋅∣Σ∣⋅α)O(m + |V| \cdot |\Sigma| \cdot \alpha),其中 ∣Σ∣=10|\Sigma| = 10。
  • 空间:O(∣V∣⋅∣Σ∣)O(|V| \cdot |\Sigma|),即约 2.05×105×102.05 \times 10^{5} \times 10 个状态格子; C++ 版实测峰值内存 1010 MB(限时 512512 MB)。
  • I/O 才是本题的大头:Slen⩽8×106S_{\text{len}} \leqslant 8 \times 10^{6},输出可达 10510^{5} 行。 C++ 版用 ios::sync_with_stdio(false) + '\n' 逐行输出; Python 版把答案先收进列表再 '\n'.join 一次性写出,避免 10510^{5} 次 print。
  • Python 实测:最重的两个点(problem6 97946 次询问、problem9 97949 次询问) 各约 0.110.11 s;即便是手工构造的"每个询问都走满 50 步再落空"的 Slen≈107S_{\text{len}} \approx 10^{7} 极端输入,CPython 也只用 0.260.26 s, 远低于 10001000 ms 限时,本题对 Python 没有可预见的超时风险。 关键在于"按空白切分整块读入 + 一次写出",而不是逐行 input / print。

总结

  • 纠缠 = 右语言等价,是本题的题眼。 想通 “a+X∈S  ⟺  b+X∈Sa + X \in S \iff b + X \in S 对一切 XX” 就是 Myhill–Nerode 等价,无穷多个串的插入就神奇地退化成一次"合并两个状态"。
  • 等价类对出边封闭。 合并 u,vu, v 必须连 u.cu.c 与 v.cv.c 一起合并,且要闭包到底; 漏掉闭包会在"纠缠后再加入新串"的用例上错答。
  • 查询每步跳代表元。 等价类动态变化,trie 的边不是静态父子指针, 任何"缓存的代表元"都可能过时。
  • 加入操作是单向的。 fin 只置真不置假,等价类只并不拆, 于是从始至终没有一行撤销代码——这一点直接源自题面"只增不减的集合"。
  • 小心 2 操作的串可以超出 LL。 询问串长度只受 SlenS_{\text{len}} 限制, trie 里走不通的前缀要立刻返回 00,不要为询问串开点,否则节点数会爆。

备注(关于本题素材)

本题素材源目录带数据生成脚本,data/ 是自造数据,content.md 的题面是按网络流传的 一本通《量子纠缠》重建的,出题意图与官方原题可能有偏差,需注意以下几点:

  • 题面【提示】里的 P≡m(mod10)P \equiv m \pmod{10} 中 PP 未作任何解释;生成器按 "P=P = 测试点编号"解读,并对每个测试点令 m≡m \equiv 点号 (mod10)\pmod{10}。
  • 题面样例的期望输出末两行带多余制表符(0\t / 1\t), 应为排版残留,按 1/01/0 逐行比对即可。
  • 素材源的 std.cpp 已在本机编译并与 data/ 全部 10 个测试点的 .out 逐一比对, 10/10 逐字节一致,其"并查集 + trie 出边闭包"的建模与本文推导一致, 因此本文的 main.cpp 沿用同一建模(重写实现,未照抄源码)。