反对称串由前 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
形式化题目
给定正整数
求同时满足下列两条的
是反对称的; - 每个
都是 的子串(连续子串)。
记
正解
思路
第一步:反对称把自由度砍一半。 反对称条件把位置
反过来每个
“数
第二步:
-
左半段:
,此时 完全落在 里,等价于 是 的子串; -
右半段:
,此时 完全落在 里。 把等式两边同时反转取反: 是 的子串 是 的子串。记 于是这一类等价于是 的子串; -
横跨中点:
。设左侧部分长度为 ( ), 左侧就是 的后缀 位,右侧 位落在右半段里。右侧第 位是 ,展开后可以验证右侧恰好由 的后缀 位决定,并且要求 (把
代进去: 的第 位是 , 两条式子拼起来正好补出完整的 。)
第三类是麻烦所在:它同时要求
第三步:
第四步:横跨中点的条件可以退化成一个后缀条件。 设
- 若
:需要 的后 位等于 ,再要求 以 结尾; - 若
:需要 的后 位等于 ,再要求 以 结尾。
而
注意中点标记不能在 DP 途中结算:它约束的是
第五步:DP。 状态是(当前 trie 节点
每次读入一个字符
样例推演。 样例
| 含 |
含 |
计入 | ||
|---|---|---|---|---|
| 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 |
表中
边界情况:若某个
代码
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++ 版(同一算法):
/**
* 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 节点数
,掩码状态数 , 转移是 。总时间 ,取满时约 次转移。 实测 C++ 最慢的点 0.04 s(限时 1000 ms),Python 最慢的点 2.1 s。 - 空间:两个滚动数组
、 ,共 个 int, 约MB,加上 trie 本身, 实测峰值内存 8.3 MB(限时 256 MB)。 - 与 C++ 解法的关系:两份代码是同一算法、同一状态定义,连变量名都一一对应
(
hit/mid_all对应hitMask/midAll)。Python 版把"掩码不变"的那一支 整行交给map(add, ...)走 C 循环,最慢的点仍在 2 s 出头,在 1000 ms 限时下会 TLE; 按短解法规范这里不换算法(枚举个 的暴力在 之外完全不可行)。
总结
- 先用对称性参数化,再谈统计:反对称把
个候选压到 个( 由前 位 唯一决定),这一步就把问题从"数串"变成了"数 "。 - 用"替身串"消掉右半段:
把" 出现在 里"翻译成" 出现在 里", 于是左、右两类命中都变成 AC 自动机上的同一个动作, 与 还能共用一位掩码。 - 剩下的一类命中退化成一个后缀条件:“
同时以 、 结尾"等价于"较短者是较长者的 后缀,且 以较长者结尾”。 、 都是模式的前缀,所以标记只需打在已存在的 trie 节点上。 - 约束在哪结算,就放在哪一步:
是"走过就算"的,边走边记; 是" 的末尾"的约束,必须留到 造完后按 fail 链结算。 把这两类混在一起是本题最容易写错的地方。 - 实现陷阱:滚动数组用二维数组时,
memset/memcpy的长度要按行宽 逐行处理,不能写成"节点数 × 状态数"——当时后者小于数组实际跨度, 会静默漏清、漏拷后面若干行, 的数据却全部正确。 - 关于本题数据:素材源里带数据生成脚本(
data.py),data/的.out是用配套标程 现场生成的,因此"通过 10 个点"只说明与标程自洽,不等于官方 AC。本解未照抄标程, 另外用"枚举全部个 并逐个子串检查"的暴力做了 400 组小规模随机对拍 ( 、 ,含长于 的模式、重复模式、以及取自真实解的窗口), 两份实现全部一致;题面本身为网络重建,出题意图可能与官方原题存在偏差。