把 m 条子串相等限制化成位置的并查集,用倍增分层(ST 表思想)把每条限制压到 O(log n) 次合并,最后按连通块数算 9×10^(t-1)。
OJ: roj
题目 ID: 1748
难度:提高+/省选-
标签:并查集倍增ST表python
创建: 2026-10-07 21:08
更新: 2026-10-07 21:08
形式化题目
求长度为
即两个等长子串逐位相同。输入保证
约束:
换个说法:把
目标是求这个等式系统的解数。另外
正解
思路
朴素做法。 用并查集维护"哪些位置必须取相同数字"。对第 unite(l1+d, l2+d)。全部限制处理完后,设并查集有
瓶颈在哪? 朴素做法本身没有逻辑错误,问题是一条限制的代价是
关键观察:一条"整段相等"的等式可以拆成两条"半段相等"。 若区间
每条限制只用两次合并。 对长度
为什么这是等价的? 记
分层并查集(逆用 ST 表)。 由上可知,只需要
自顶向下下放(这一步就是"逆用 ST 表")。 现在关系都在高层,第
- 先取
,即与第 个区间同属一个集合的代表元区间; - 把"第
个区间 第 个区间"拆成两对更短的区间:
第
统计答案。 全部下放完成后,第
举一个最小的例子验证拆分的"重叠覆盖":1 3 4 6(S[1..3] = S[4..6]。
题面给的例子 123123、351351 都满足它,131141 违反
代码
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 21:02
# update_at: 2026-10-07 21:02
import sys
MOD = 10 ** 9 + 7 # 答案的模数;首位块的 9 种选择不参与取幂
# 分层并查集:layers[k] 这一层刻画的是"以 i 开头、长度 2^k 的区间"之间的相等关系,
# 所以层号 k 唯一决定了元素含义,下放时不必再携带区间长度;下标 0 留空不用。
type Par = list[int] # 一层的父指针表
type Size = list[int] # 一层的连通块大小表
def find(par: Par, x: int) -> int:
"""找 x 所在集合的代表元,顺路做路径减半压缩。"""
while par[x] != x:
par[x] = par[par[x]]
x = par[x]
return x
def unite(par: Par, size: Size, a: int, b: int) -> None:
"""把 a、b 两个集合合并(按大小启发式,摊还近似 O(α))。"""
a, b = find(par, a), find(par, b)
if a == b:
return
if size[a] < size[b]:
a, b = b, a
par[b] = a
size[a] += size[b]
def add_constraint(layers: list[Par], sizes: list[Size], l1: int, r1: int, l2: int, r2: int) -> None:
"""把一条"子串相等"限制压成两次区间合并。
取 k = floor(log2 L),两段长度 2^k 的窗口各自从两端对齐,因为 2*2^k >= L
它们必然重叠并盖满 [l1,r1] 与 [l2,r2],所以与"整段相等"完全等价。
"""
k = (r1 - l1 + 1).bit_length() - 1
step = 1 << k
unite(layers[k], sizes[k], l1, l2)
unite(layers[k], sizes[k], r1 - step + 1, r2 - step + 1)
def push_down(layers: list[Par], sizes: list[Size], n: int, k: int) -> None:
"""把第 k 层的相等关系下放到第 k-1 层:两个 2^k 区间相等 ⟹ 两对半长区间分别相等。"""
par, size = layers[k], sizes[k]
span, half = 1 << k, 1 << (k - 1)
for i in range(1, n - span + 2): # i 的合法范围即 i + span - 1 <= n
root = find(par, i)
if root == i:
continue # i 自己就是代表元,没有信息要往下传
unite(layers[k - 1], sizes[k - 1], i, root)
unite(layers[k - 1], sizes[k - 1], i + half, root + half)
def answer_after_merges(layers: list[Par], n: int) -> int:
"""由完全下放后的第 0 层相等关系得答案:首位所在块只能取 1..9,其余每块各 0..9。"""
blocks = sum(1 for i in range(1, n + 1) if find(layers[0], i) == i) # 自由变量个数
return 9 * pow(10, blocks - 1, MOD) % MOD
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
max_log = n.bit_length() - 1 # floor(log2 n),实际用到的最高层号
layers: list[Par] = [list(range(n + 1)) for _ in range(max_log + 1)]
sizes: list[Size] = [[1] * (n + 1) for _ in range(max_log + 1)]
for _ in range(m):
l1, r1, l2, r2 = next(data), next(data), next(data), next(data)
add_constraint(layers, sizes, l1, r1, l2, r2)
for k in range(max_log, 0, -1):
push_down(layers, sizes, n, k)
print(answer_after_merges(layers, n))
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 21:02
* update_at: 2026-10-07 21:02
*/
// 一本通 1748《大数计数》
// 题意:长度为 n 的大数 S_1..S_n,S_1 是最高位所以不能为 0;
// 给出 m 条限制 (l1,r1,l2,r2),要求子串 S[l1..r1] 与 S[l2..r2] 完全相同;
// 求满足全部限制的 n 位数个数,模 1e9+7。
//
// 模型:把 n 个位置看成 n 个变量,每条限制等价于"对应位置两两相等",
// 于是用并查集维护位置的相等关系;设最终连通块数为 t,
// 最高位所在块只能取 1..9,其余每块取 0..9,答案 = 9 * 10^(t-1)。
//
// 瓶颈:朴素地逐位合并,一条长为 L 的限制要 O(L) 次合并,总代价 O(nm)。
// 破法:倍增(ST 表思想)+ 并查集。第 k 层并查集刻画"以 i 开头、长度 2^k
// 的区间"之间的相等关系。一条长为 L 的限制取 k = floor(log2 L),
// 用两段长度 2^k 的重叠区间把 [l1,r1] 与 [l2,r2] 各自盖满,等价性不变。
// 最后自顶向下把高层关系下放到低两层(逆用 ST 表),
// 统计第 0 层连通块数即可。
//
// 复杂度 O((n+m) log n α(n)),空间 O(n log n)。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005; // n 的上限
const int LOG = 18; // 2^17 = 131072 > 1e5,层号 0..17 足够
const int MOD = 1000000007;
typedef long long ll;
// 一层并查集:第 k 层上的元素是区间 [i, i + 2^k - 1],i 取 1..n-2^k+1
struct Layer {
int fa[MAXN]; // fa[i]:区间 [i, i+2^k-1] 的代表元
int sz[MAXN]; // 按大小合并时的连通块大小
};
Layer layer[LOG]; // layer[k] 就是第 k 层
int pw[LOG]; // pw[k] = 2^k
ll n, m;
int max_log; // floor(log2 n),实际用到的最高层号
// 第 k 层上找 x 的代表元(迭代路径压缩,避免递归过深)
int find_layer(int k, int x) {
int root = x;
while (layer[k].fa[root] != root) {
root = layer[k].fa[root];
}
while (layer[k].fa[x] != root) {
int nxt = layer[k].fa[x];
layer[k].fa[x] = root;
x = nxt;
}
return root;
}
// 第 k 层上合并两个区间,按大小启发式
void unite_layer(int k, int a, int b) {
a = find_layer(k, a);
b = find_layer(k, b);
if (a == b) {
return;
}
if (layer[k].sz[a] < layer[k].sz[b]) {
int tmp = a;
a = b;
b = tmp;
}
layer[k].fa[b] = a;
layer[k].sz[a] += layer[k].sz[b];
}
void read_input() {
cin >> n >> m;
}
void solve() {
pw[0] = 1;
for (int k = 1; k < LOG; k++) {
pw[k] = pw[k - 1] << 1;
}
max_log = 0;
while (max_log + 1 < LOG && pw[max_log + 1] <= n) {
max_log++;
}
// 每层初始化:区间自己成一个集合
for (int k = 0; k <= max_log; k++) {
for (int i = 1; i <= n; i++) {
layer[k].fa[i] = i;
layer[k].sz[i] = 1;
}
}
// 加入限制:k = floor(log2 L),用两段 2^k 区间盖住整段,等价性不变
for (ll q = 1; q <= m; q++) {
ll l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
int len = r1 - l1 + 1;
int k = 0;
while (pw[k + 1] <= len) {
k++;
}
unite_layer(k, l1, l2);
unite_layer(k, r1 - pw[k] + 1, r2 - pw[k] + 1);
}
// 逆用 ST 表:自顶向下把"两个 2^k 区间相等"拆成两个"2^(k-1) 区间相等"
for (int k = max_log; k >= 1; k--) {
int half = pw[k - 1];
for (ll i = 1; i + pw[k] - 1 <= n; i++) {
int p = find_layer(k, i);
if (p == i) {
continue; // 自己就是代表元,下放没有信息可传
}
unite_layer(k - 1, i, p);
unite_layer(k - 1, i + half, p + half);
}
}
// 统计第 0 层(一个个位置)的连通块数
ll blocks = 0;
for (ll i = 1; i <= n; i++) {
if (find_layer(0, i) == i) {
blocks++;
}
}
ll ans = 9; // 最高位所在块:1..9
for (ll i = 1; i < blocks; i++) {
ans = ans * 10 % MOD; // 其余每块:0..9
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
- 时间:每条限制
次分层合并(合并本身 );下放阶段共 次查找与合并;统计 。总计 ( 为反阿克曼函数,实际近似常数)。 与朴素 相比,在 时从 降到约 次并查集操作。 - 空间:C++ 版开
层( 时为 层,数组上限取 ), 每层两个长度为 的 int数组,约MB, 远低于 512 MB 限制;Python 版是 个长度为 的 list,常数大得多但同样可接受。 - 实现细节:第
层只需给 初始化,但我为省事把 全初始化了,多出来的位置永远用不到、不影响正确性。 下放阶段加了一句 if (p == i) continue;:此时自己就是代表元,两对拆分都是自等, 合并它没有任何信息量,跳过可以省掉大量无用的 find。 - 限时:题目限时 1000 ms。C++ 版实测在顶格点(
)上远低于 100 ms; Python 版在同样的点上明显更慢,属于 Python 语言的常数问题,而非算法差异。
总结
- 先化简模型,再谈数据结构:题面讲的是"大数字符串相等",但一旦把位置看成变量,
问题就只剩"哪些位置必须相同" —— 本质是等价类计数,与具体数字无关,
连"数有多少种取值"这件事都被压缩成了一个
的式子。 - 能拆就能省:一段长等式可以无损劈成两段半长等式,这既是可拆分性、也是可替代性。
利用它把"长度
的等式"换成"两段长度 的等式", 覆盖的正确性依赖于 ,也就是两个窗口一定会重叠。 - 逆用 ST 表:ST 表是"用两段短区间合成一段长区间",这里反过来 ——
先在高层(长区间)记账,再从高到低把账往下滚。分层编号
与区间长度 绑定, 所以下放时不需要任何额外的区间长度信息,只靠层号就能定位拆分点。 - 边界:
时答案恒为 (一位数 ); 条限制全是自等 (如 i i i i)时不做任何合并,,答案 ; 同一对位置被多组限制重复约束时并查集自动去重,不需要特判。 - 数据说明:本题素材自带数据生成脚本
data.py,data/是据此自造的 (共 10 个点,含的边界、可解析验证的结构点、以及 的顶格随机点), 题面本身是从一本通《高手训练》重建的;经比对,本题与 [SCOI2016] 萌萌哒 (洛谷 P3295 / BZOJ 4569)完全同题, 的范围也一致。 因此下的结论只保证对这份自造数据成立,不宣称等于官方原题数据。