串包含问题

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

反对称串由前 m 位 T 唯一确定;把 p 与 ~reverse(p) 一起建成 AC 自动机,用 2^n 掩码逐位 DP,跨中点的命中留到末尾结算。

OJ: roj

题目 ID: 1706

难度:提高+/省选-

标签:字符串AC 自动机状态压缩动态规划python

创建: 2026-10-07 17:20

更新: 2026-10-07 17:20

形式化题目

给定正整数 mm 与 nn 个 0101 串 s1,…,sns_1, \dots, s_n。称长度 2m2m 的 0101 串 SS 是反对称的,当且仅当

S[i]≠S[2m−i+1](1⩽i⩽2m).S[i] \neq S[2m - i + 1] \qquad (1 \leqslant i \leqslant 2m).

求同时满足下列两条的 SS 的个数,对 998244353998244353 取模:

  1. SS 是反对称的;
  2. 每个 sjs_j 都是 SS 的子串(连续子串)。

记 T=S[1⋅m]T = S[1 \cdot m] 为 SS 的前 mm 位, ⋅ ‾\overline{\,\cdot\,} 表示按位取反。

正解

思路

第一步:反对称把自由度砍一半。 反对称条件把位置 ii 与 2m−i+12m-i+1 绑成一对, 每对里两个字符必须相反。2m2m 个位置正好分成 mm 对,每一对自由选 22 种,所以 长度为 2m2m 的反对称串共有 2m2^m 个。更精确地说,SS 由前 mm 位 TT 唯一决定:

S=T+reverse⁡(T)‾=T+qT,qT=reverse⁡(T)‾.S = T + \overline{\operatorname{reverse}(T)} = T + q_T, \qquad q_T = \overline{\operatorname{reverse}(T)} .

反过来每个 T∈{0,1}mT \in \{0,1\}^m 都给出一个合法的反对称串,于是

答案=#{ T∈{0,1}m:T+reverse⁡(T)‾ 含全部 sj }.\text{答案} = \#\{\, T \in \{0,1\}^m : T + \overline{\operatorname{reverse}(T)} \text{ 含全部 } s_j \,\}.

“数 SS” 变成了 “数 TT”,规模从 22m2^{2m} 降到 2m2^m。

第二步:sjs_j 在 SS 中的出现位置只有三类。 记模式 p=sjp = s_j、长度 LL,它的一个出现是区间 [a,a+L−1][a, a+L-1](00 下标)。按这个区间与中点的关系分三类:

  • 左半段:a+L−1⩽m−1a + L - 1 \leqslant m-1,此时 pp 完全落在 TT 里,等价于 pp 是 TT 的子串;

  • 右半段:a⩾ma \geqslant m,此时 pp 完全落在 qT=reverse⁡(T)‾q_T = \overline{\operatorname{reverse}(T)} 里。 把等式两边同时反转取反:pp 是 reverse⁡(T)‾\overline{\operatorname{reverse}(T)} 的子串   ⟺  \iff reverse⁡(p)‾\overline{\operatorname{reverse}(p)} 是 TT 的子串。记

    q=reverse⁡(p)‾,q = \overline{\operatorname{reverse}(p)},
    于是这一类等价于 qq 是 TT 的子串;

  • 横跨中点:a<m⩽a+L−1a < m \leqslant a+L-1。设左侧部分长度为 k=m−ak = m - a(1⩽k⩽L−11 \leqslant k \leqslant L-1), 左侧就是 TT 的后缀 kk 位,右侧 L−kL-k 位落在右半段里。右侧第 ii 位是 T[m−1−i]‾\overline{T[m-1-i]},展开后可以验证右侧恰好由 TT 的后缀 L−kL-k 位决定,并且要求

    T 的后缀 k 位=p[0..k),T 的后缀 L−k 位=q[0..L−k).T \text{ 的后缀 } k \text{ 位} = p[0..k), \qquad T \text{ 的后缀 } L-k \text{ 位} = q[0..L-k).

    (把 q=reverse⁡(p)‾q = \overline{\operatorname{reverse}(p)} 代进去:qq 的第 ii 位是 p[L−1−i]‾\overline{p[L-1-i]}, 两条式子拼起来正好补出完整的 pp。)

第三类是麻烦所在:它同时要求 TT 的两个后缀等于两条不同串的前缀。

第三步:pp 与 qq 一起进 AC 自动机。 前两类都是"某个串是不是 TT 的子串", 这正是 AC 自动机擅长的:把 pjp_j 与 qjq_j 都插进同一棵 trie,共用第 jj 位掩码—— pjp_j 与 qjq_j 中任意一个出现,都意味着模式 jj 已经被 SS 包含。建 fail 指针时沿链累积出 hit[u]\mathrm{hit}[u]:TT 走到节点 uu 时,所有以 TT 的某个后缀出现的模式集合。

第四步:横跨中点的条件可以退化成一个后缀条件。 设 A=p[0..k)A = p[0..k)(长度 kk)、B=q[0..L−k)B = q[0..L-k)(长度 L−kL-k),第三类要求 TT 同时以 AA、BB 结尾。 两个后缀条件同时成立,当且仅当较短者是较长者的后缀,且 TT 以较长者结尾:

  • 若 k>L−kk > L-k:需要 AA 的后 L−kL-k 位等于 BB,再要求 TT 以 AA 结尾;
  • 若 k⩽L−kk \leqslant L-k:需要 BB 的后 kk 位等于 AA,再要求 TT 以 BB 结尾。

而 AA、BB 分别是 pp、qq 的前缀,它们在 trie 上的节点在插入时就已经存在了。 于是对每个可行的 kk 检查一次后缀关系,成立就在"较长前缀"的节点上打一个中点标记 mid[u]\mathrm{mid}[u];DP 结束后,若终点 uu 的 fail 链上带着该标记(累积成 midAll[u]\mathrm{midAll}[u]), 就说明 TT 以对应前缀结尾,第三类成立。

注意中点标记不能在 DP 途中结算:它约束的是 TT 的末尾(也就是中点)那一小段, 只有把 TT 整串造完,才知道末尾停在哪。所以 nn 个模式分成"边走边记"的 hit\mathrm{hit} 与"末尾一次性补上"的 midAll\mathrm{midAll} 两部分。

第五步:DP。 状态是(当前 trie 节点 uu,已命中模式集合 maskmask):

dp[u][mask]=#{ T 的某个前缀: 走到的节点是 u, 命中集合恰为 mask }.\mathrm{dp}[u][mask] = \#\{\, T \text{ 的某个前缀} : \text{ 走到的节点是 } u,\ \text{命中集合恰为 } mask \,\}.

每次读入一个字符 cc,转移到 v=go[u][c]v = \mathrm{go}[u][c],掩码变成 mask∣hit[v]mask \mid \mathrm{hit}[v]。 mm 步之后答案就是

∑u∑mask[ (mask∣midAll[u])=fullMask ]⋅dp[u][mask].\sum_{u} \sum_{mask} [\, (mask \mid \mathrm{midAll}[u]) = \text{fullMask} \,] \cdot \mathrm{dp}[u][mask] .

样例推演。 样例 n=2n=2、m=3m=3、模式 011011 与 001001,共 23=82^3 = 8 个候选 TT:

TT S=T+reverse⁡(T)‾S = T + \overline{\operatorname{reverse}(T)} 含 011011 含 001001 计入
000 000111 ✅ 位置 2(跨中点) ✅ 位置 1(跨中点) 1
001 001011 ✅ 位置 3(右半段) ✅ 位置 0(左半段) 1
010 010101 ❌ ❌ 0
011 011001 ✅ 位置 0(左半段) ✅ 位置 3(右半段) 1
100 100110 ✅ 位置 2(跨中点) ✅ 位置 1(跨中点) 1
101 101010 ❌ ❌ 0
110 110100 ❌ ❌ 0
111 111000 ❌ ❌ 0

表中 T=000T=000 的 S=000111S=000111:001001 出现在位置 1、011011 出现在位置 2,两者都横跨中点 (位置 0 到 2 是左半段),走的正是第四步的中点标记。以 011011 为例,a=2a=2 给出 k=m−a=1k = m - a = 1,条件退化成"TT 的后 11 位等于 p[0..1)=0p[0..1) = 0 且 TT 的后 22 位等于 q[0..2)q[0..2)",而 q=reverse⁡(011)‾=001q = \overline{\operatorname{reverse}(011)} = 001,T=000T=000 两条都满足。 再看 T=001T=001 的 S=001011S=001011:001001 落在左半段(它就是 TT 的子串), 011011 落在右半段位置 3——它的替身串 q=reverse⁡(011)‾=001q = \overline{\operatorname{reverse}(011)} = 001 恰好就是 TT 本身,这正是第二步"把右半段的匹配搬到 TT 上"的效果。 最后统计得 44,与样例输出一致。

边界情况:若某个 ∣sj∣>2m|s_j| > 2m,它无论如何都放不进 SS。在自动机里,pjp_j、qjq_j 的节点深度 都大于 mm,TT 走不到,中点标记要求的前缀长度 k⩽mk \leqslant m 也取不到,于是第 jj 位永远 不可能被置上,答案自然是 00,不需要特判。

代码

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

import sys
from operator import add

MOD = 998244353
# 模式掩码:第 j 位(1 << j)表示第 j 个模式已经在 S 里出现过;
# p 与 q = ~reverse(p) 共用同一位,因为两者任一出现都意味着该模式被 S 包含。

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Go = list[list[int]]    # go[u] = 节点 u 读入 0 / 1 之后到达的节点
type Mask = list[int]        # 每个节点一个 2^n 掩码
type Rows = list[list[int]]  # DP 表:节点 -> 该节点上各掩码的方案数


def comp_rev(s: str) -> str:
    """返回 ~reverse(s):p 出现在右半段 <=> q = ~reverse(p) 出现在 T 里。"""
    return ''.join('1' if c == '0' else '0' for c in reversed(s))


def insert(s: str, bit: int, go: Go, end: Mask) -> list[int]:
    """把 s 插进 trie,返回每个前缀的节点编号(第 k 项是长度 k 的前缀)。"""
    path = [0]
    u = 0
    for c in s:
        v = go[u][ord(c) - 48]
        if v < 0:
            go.append([-1, -1])  # 新节点:end 与节点一一对应,一起长
            end.append(0)
            v = len(go) - 1
            go[u][ord(c) - 48] = v
        u = v
        path.append(u)
    end[u] |= bit
    return path


def build_automaton(pats: list[str]) -> tuple[Go, Mask, Mask]:
    """插入 p 与 q 并建好 AC 自动机,返回 (转移表, 命中掩码, 中点掩码)。"""
    go: Go = [[-1, -1]]
    end = [0]
    pnode = [insert(p, 1 << j, go, end) for j, p in enumerate(pats)]
    qnode = [insert(comp_rev(p), 1 << j, go, end) for j, p in enumerate(pats)]
    mid = [0] * len(go)  # 中点标记与节点一一对应,插入阶段先空着

    # 横跨中点:左侧匹配 k 位(1 <= k <= L-1)时,左侧是 T 的后缀 k 位、
    # 必须等于 p 的前 k 位;右侧由 T 的后缀 L-k 位决定、必须等于 q 的前 L-k 位。
    # 两者同时成立 <=> 较短者是较长者的后缀,且 T 以较长者结尾,
    # 所以只需在"较长前缀"的节点上打标记,末尾看 T 是否停在这种节点上。
    for j, p in enumerate(pats):
        L = len(p)
        q = comp_rev(p)
        for k in range(1, L):
            if k > L - k:                       # 较长者是 p 的前 k 位
                if p[k - (L - k):k] == q[:L - k]:
                    mid[pnode[j][k]] |= 1 << j
            elif q[L - 2 * k:L - k] == p[:k]:   # 较长者是 q 的前 L-k 位
                mid[qnode[j][L - k]] |= 1 << j

    # 根节点缺的儿子指向自己;其余节点在 BFS 里补全成自动机转移,
    # 顺带沿 fail 链累积"命中"与"中点"两类掩码。
    for c in (0, 1):
        go[0][c] = max(go[0][c], 0)
    fail = [0] * len(go)
    hit = end[:]
    mid_all = mid[:]
    queue = [v for v in go[0] if v > 0]
    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        hit[u] |= hit[fail[u]]
        mid_all[u] |= mid_all[fail[u]]
        for c in (0, 1):
            v = go[u][c]
            if v < 0:
                go[u][c] = go[fail[u]][c]
            else:
                fail[v] = go[fail[u]][c]
                queue.append(v)
    return go, hit, mid_all


def count_strings(m: int, go: Go, hit: Mask, mid_all: Mask, full: int) -> int:
    """逐位构造 T:dp[节点][已命中掩码],末尾并入中点标记后统计覆盖全部模式的方案数。"""
    states = full + 1
    dp: Rows = [[0] * states for _ in range(len(go))]
    dp[0][0] = 1
    for _ in range(m):
        ndp: Rows = [[0] * states for _ in range(len(go))]
        for u, row in enumerate(dp):
            if not any(row):  # 这个节点上没有方案,两条出边都不用走
                continue
            for c in (0, 1):
                v = go[u][c]
                added = hit[v]
                tgt = ndp[v]
                if added:  # 命中集合变大:把并到同一个新掩码的来源逐个相加
                    for mask in range(states):
                        x = row[mask]
                        if x:
                            nm = mask | added
                            s = tgt[nm] + x
                            tgt[nm] = s - MOD if s >= MOD else s
                else:      # 命中集合不变:整行同位置相加,交给 map 走 C 循环
                    merged = [s - MOD if s >= MOD else s for s in map(add, tgt, row)]
                    ndp[v] = merged
        dp = ndp
    # 自动机转移是完整的,dp 永远有非零项,不需要提前退出
    return sum(cnt for u, row in enumerate(dp) for mask, cnt in enumerate(row)
               if mask | mid_all[u] == full) % MOD


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().split())
    n, m = int(next(tokens)), int(next(tokens))
    pats = [next(tokens).decode() for _ in range(n)]
    go, hit, mid_all = build_automaton(pats)
    print(count_strings(m, go, hit, mid_all, (1 << n) - 1))


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

// 一本通 1706《串包含问题》
// 长度为 2m 的反对称串 S 由前 m 位 T 唯一确定:S = T + ~reverse(T),
// 于是"数 S"变成"数 T"。把模式 p 和它的右半段替身 q = ~reverse(p) 一起插进
// AC 自动机,逐位构造 T 做 DP,用 2^n 的掩码记已经命中的模式;
// 横跨中点的命中无法边走边判,改成在"较长前缀"的节点上打标记、末尾一次性结算。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 998244353;
const int MAXN = 6;                        // 模式个数上限
const int MAXLEN = 100;                    // 单个模式长度上限
const int MAXNODE = 1 + 2 * MAXN * MAXLEN; // AC 自动机节点数上限:1 + 2 * sum|s_i|

struct Node {
    int ch[2];    // 0/1 字符的转移,建好 fail 后补全成自动机转移
    int fail;     // 失配指针
    int endMask;  // 以该节点结尾的模式掩码(p 与 q 共用同一位)
    int midMask;  // 只有"T 以该节点结尾"才成立的中点命中标记
    int hitMask;  // 沿 fail 链累积的 endMask:T 已把该模式当后缀用上
    int midAll;   // 沿 fail 链累积的 midMask
};
Node node[MAXNODE]; // 动态化静态:节点 u 就是 node[u]
int nodeCnt;        // 已经开出的节点个数,根节点固定为 0

struct Pattern {
    string p;             // 原串
    string q;             // ~reverse(p):p 出现在右半段 <=> q 出现在 T 里
    int len;              // 模式长度
    int pNode[MAXLEN + 1]; // pNode[k] = p 的前 k 位在 trie 上的节点编号
    int qNode[MAXLEN + 1]; // qNode[k] = q 的前 k 位在 trie 上的节点编号
};
Pattern pat[MAXN];

int dp[MAXNODE][1 << MAXN];  // dp[u][mask]:T 走到节点 u、已命中模式集合为 mask 的方案数
int ndp[MAXNODE][1 << MAXN]; // 下一层的滚动数组

// 新建一个节点(动态开点),返回编号
int new_node() {
    nodeCnt++;
    node[nodeCnt].ch[0] = node[nodeCnt].ch[1] = 0;
    node[nodeCnt].fail = 0;
    node[nodeCnt].endMask = node[nodeCnt].midMask = 0;
    node[nodeCnt].hitMask = node[nodeCnt].midAll = 0;
    return nodeCnt;
}

// 把串 s 插进 trie,同时把每个前缀的节点编号记到 path 里
void insert(const string& s, int bit, int path[]) {
    int u = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
        int c = s[i] - '0';
        if (!node[u].ch[c]) node[u].ch[c] = new_node();
        u = node[u].ch[c];
        path[i + 1] = u;
    }
    node[u].endMask |= 1 << bit; // p 与 q 都算"模式 bit 被 T 包含"
}

// BFS 建 fail 指针、补全自动机转移,并沿 fail 链累积两类命中掩码
void build() {
    queue<int> que;
    node[0].hitMask = node[0].endMask;
    node[0].midAll = node[0].midMask;
    for (int c = 0; c < 2; ++c) {
        int v = node[0].ch[c];
        if (v) {
            node[v].fail = 0;
            que.push(v);
        } else {
            node[0].ch[c] = 0; // 根的缺失转移指向自己
        }
    }
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        node[u].hitMask = node[u].endMask | node[node[u].fail].hitMask;
        node[u].midAll = node[u].midMask | node[node[u].fail].midAll;
        for (int c = 0; c < 2; ++c) {
            int v = node[u].ch[c];
            if (v) {
                node[v].fail = node[node[u].fail].ch[c];
                que.push(v);
            } else {
                node[u].ch[c] = node[node[u].fail].ch[c];
            }
        }
    }
}

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    nodeCnt = 0; // 根节点 0 不用开点
    int fullMask = 0;
    for (int j = 0; j < n; ++j) {
        cin >> pat[j].p;
        pat[j].len = pat[j].p.size();
        pat[j].q = pat[j].p;
        reverse(pat[j].q.begin(), pat[j].q.end());
        for (int i = 0; i < pat[j].len; ++i)
            pat[j].q[i] = (pat[j].q[i] == '0') ? '1' : '0';
        fullMask |= 1 << j;
        insert(pat[j].p, j, pat[j].pNode);
        insert(pat[j].q, j, pat[j].qNode);
    }

    // 横跨中点的命中:设左侧匹配 k 位(1 <= k <= L-1),左侧是 T 的后缀 k 位、
    // 必须是 p 的前 k 位;右侧由 T 的后缀 L-k 位决定、必须是 q 的前 L-k 位。
    // 两者同时成立 <=> 较长者以较短者为后缀,且 T 以较长者结尾。
    for (int j = 0; j < n; ++j) {
        const string& p = pat[j].p;
        const string& q = pat[j].q;
        int L = pat[j].len;
        for (int k = 1; k <= L - 1; ++k) {
            if (k > L - k) {
                // 较长者是 A = p 的前 k 位,要求 A 的后 L-k 位等于 B = q 的前 L-k 位
                if (p.compare(k - (L - k), L - k, q, 0, L - k) == 0)
                    node[pat[j].pNode[k]].midMask |= 1 << j;
            } else {
                // 较长者是 B = q 的前 L-k 位,要求 B 的后 k 位等于 A = p 的前 k 位
                if (q.compare((L - k) - k, k, p, 0, k) == 0)
                    node[pat[j].qNode[L - k]].midMask |= 1 << j;
            }
        }
    }

    build();

    int nodes = nodeCnt + 1;  // 节点编号 0..nodeCnt
    int states = 1 << n;      // 已命中模式的集合
    dp[0][0] = 1;
    for (int step = 0; step < m; ++step) {
        // 行宽固定是 1 << MAXN,DP 只用前 states 列,所以逐行清零 / 逐行拷贝
        for (int u = 0; u < nodes; ++u) memset(ndp[u], 0, sizeof(int) * states);
        for (int u = 0; u < nodes; ++u) {
            for (int mask = 0; mask < states; ++mask) {
                int val = dp[u][mask];
                if (!val) continue;
                for (int c = 0; c < 2; ++c) {
                    int v = node[u].ch[c];
                    int nm = mask | node[v].hitMask;
                    int t = ndp[v][nm] + val;
                    ndp[v][nm] = (t >= MOD) ? t - MOD : t;
                }
            }
        }
        for (int u = 0; u < nodes; ++u) memcpy(dp[u], ndp[u], sizeof(int) * states);
    }

    // T 已经完整,横跨中点的命中此时才结算:要求节点 u 代表的后缀带上 mid 标记
    ll ans = 0;
    for (int u = 0; u < nodes; ++u) {
        for (int mask = 0; mask < states; ++mask) {
            if ((mask | node[u].midAll) == fullMask) {
                ans += dp[u][mask];
                if (ans >= MOD) ans -= MOD;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

复杂度

  • 时间:trie 节点数 V⩽1+2∑∣sj∣⩽1201V \leqslant 1 + 2\sum |s_j| \leqslant 1201,掩码状态数 2n⩽642^n \leqslant 64, 转移是 O(1)O(1)。总时间 O(m⋅V⋅2n⋅2)O\big(m \cdot V \cdot 2^n \cdot 2\big),取满时约 500×1201×64×2≈7.7×107500 \times 1201 \times 64 \times 2 \approx 7.7 \times 10^7 次转移。 实测 C++ 最慢的点 0.04 s(限时 1000 ms),Python 最慢的点 2.1 s。
  • 空间:两个滚动数组 dp\mathrm{dp}、ndp\mathrm{ndp},共 O(V⋅2n)O(V \cdot 2^n) 个 int, 约 2×1201×64×4B≈0.62 \times 1201 \times 64 \times 4\text{B} \approx 0.6 MB,加上 trie 本身, 实测峰值内存 8.3 MB(限时 256 MB)。
  • 与 C++ 解法的关系:两份代码是同一算法、同一状态定义,连变量名都一一对应 (hit / mid_all 对应 hitMask / midAll)。Python 版把"掩码不变"的那一支 整行交给 map(add, ...) 走 C 循环,最慢的点仍在 2 s 出头,在 1000 ms 限时下会 TLE; 按短解法规范这里不换算法(枚举 2m2^m 个 TT 的暴力在 m⩽15m \leqslant 15 之外完全不可行)。

总结

  • 先用对称性参数化,再谈统计:反对称把 22m2^{2m} 个候选压到 2m2^m 个(SS 由前 mm 位 TT 唯一决定),这一步就把问题从"数串"变成了"数 TT"。
  • 用"替身串"消掉右半段:q=reverse⁡(p)‾q = \overline{\operatorname{reverse}(p)} 把"pp 出现在 reverse⁡(T)‾\overline{\operatorname{reverse}(T)} 里"翻译成"qq 出现在 TT 里", 于是左、右两类命中都变成 AC 自动机上的同一个动作,pjp_j 与 qjq_j 还能共用一位掩码。
  • 剩下的一类命中退化成一个后缀条件:“TT 同时以 AA、BB 结尾"等价于"较短者是较长者的 后缀,且 TT 以较长者结尾”。AA、BB 都是模式的前缀,所以标记只需打在已存在的 trie 节点上。
  • 约束在哪结算,就放在哪一步:hit\mathrm{hit} 是"走过就算"的,边走边记; mid\mathrm{mid} 是"TT 的末尾"的约束,必须留到 TT 造完后按 fail 链结算。 把这两类混在一起是本题最容易写错的地方。
  • 实现陷阱:滚动数组用二维数组时,memset / memcpy 的长度要按行宽 逐行处理,不能写成"节点数 × 状态数"——当 n<6n < 6 时后者小于数组实际跨度, 会静默漏清、漏拷后面若干行,n=6n = 6 的数据却全部正确。
  • 关于本题数据:素材源里带数据生成脚本(data.py),data/ 的 .out 是用配套标程 现场生成的,因此"通过 10 个点"只说明与标程自洽,不等于官方 AC。本解未照抄标程, 另外用"枚举全部 2m2^m 个 TT 并逐个子串检查"的暴力做了 400 组小规模随机对拍 (m⩽11m \leqslant 11、n⩽4n \leqslant 4,含长于 2m2m 的模式、重复模式、以及取自真实解的窗口), 两份实现全部一致;题面本身为网络重建,出题意图可能与官方原题存在偏差。