大数计数

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

把 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

形式化题目

求长度为 nn 的数字串 S=S1S2⋯SnS = S_1S_2\cdots S_n 的个数,其中 S1≠0S_1 \neq 0(S1S_1 是最高位), 且必须满足 mm 条限制

Sli1Sli1+1⋯Sri1  =  Sli2Sli2+1⋯Sri2,i=1,2,…,m,S_{l_{i1}}S_{l_{i1}+1}\cdots S_{r_{i1}} \;=\; S_{l_{i2}}S_{l_{i2}+1}\cdots S_{r_{i2}}, \qquad i = 1,2,\dots,m,

即两个等长子串逐位相同。输入保证 ri1−li1=ri2−li2r_{i1} - l_{i1} = r_{i2} - l_{i2}。 求方案数模 109+710^9+7 的结果。

约束:1⩽n,m⩽1051 \leqslant n, m \leqslant 10^5。

换个说法:把 nn 个位置看成 nn 个变量 S1,…,SnS_1,\dots,S_n,每条限制就是一个等式组

Sli1+d=Sli2+d(d=0,1,…,ri1−li1),S_{l_{i1}+d} = S_{l_{i2}+d} \qquad (d = 0,1,\dots,r_{i1}-l_{i1}),

目标是求这个等式系统的解数。另外 S1S_1 只允许取 1∼91 \sim 9。

正解

思路

朴素做法。 用并查集维护"哪些位置必须取相同数字"。对第 ii 条限制,逐位做 Li=ri1−li1+1L_i = r_{i1}-l_{i1}+1 次合并:unite(l1+d, l2+d)。全部限制处理完后,设并查集有 tt 个连通块, 同一个块内的位置共用一个数字、不同块互相独立,于是最高位所在块有 99 种取法(1∼91\sim9), 其余 t−1t-1 个块各有 1010 种取法,答案就是

ans=9⋅10 t−1 mod (109+7).\text{ans} = 9 \cdot 10^{\,t-1} \bmod (10^9+7).

瓶颈在哪? 朴素做法本身没有逻辑错误,问题是一条限制的代价是 O(Li)O(L_i)。 当每条限制都是长区间(Li=Θ(n)L_i = \Theta(n))而 m=105m = 10^5 时,总代价 O(nm)=1010O(nm) = 10^{10},直接崩掉。 换句话说:等式组里大多数等式是重复且冗余的,逐位合并把冗余也一起做了。

关键观察:一条"整段相等"的等式可以拆成两条"半段相等"。 若区间 [l,l+2k−1][l, l+2^k-1] 与 [l′,l′+2k−1][l', l'+2^k-1] 相等,那么把它各自劈成左右两半,两对半段也分别相等; 反过来,只要两对半段分别相等,整段就相等。所以"长度 2k2^k 的两段相等"这个关系可以无损地 往下拆成两对长度 2k−12^{k-1} 的关系。既然能拆,就能反过来用:先把长的等式用少数几个 "长度是 22 的幂"的等式覆盖住,最后再统一往下拆。

每条限制只用两次合并。 对长度 LL 的区间,取 k=⌊log⁡2L⌋k = \lfloor \log_2 L \rfloor。 长度 2k2^k 满足 2k⩽L<2k+12^k \leqslant L < 2^{k+1},也就是说两段长度 2k2^k 的窗口就够盖满长度 LL 的整段:让窗口分别从两端对齐,两个窗口必然重叠、并把 [l,r][l, r] 完整覆盖(因为 2⋅2k⩾L2 \cdot 2^k \geqslant L)。 于是限制 (l1,r1,l2,r2)(l_1,r_1,l_2,r_2) 被替换为两条"长度 2k2^k"的关系:

[l1,  l1+2k−1]=[l2,  l2+2k−1],[r1−2k+1,  r1]=[r2−2k+1,  r2].\big[l_1,\; l_1+2^k-1\big] = \big[l_2,\; l_2+2^k-1\big], \qquad \big[r_1-2^k+1,\; r_1\big] = \big[r_2-2^k+1,\; r_2\big].

为什么这是等价的? 记 d=r1−l1=r2−l2d = r_1-l_1 = r_2-l_2。第一条关系等价于 “偏移 0∼2k−10 \sim 2^k-1 的位置相等”,第二条等价于"偏移 d−2k+1∼dd-2^k+1 \sim d 的位置相等"。 两段的偏移集合之并恰好是 {0,…,d}\{0,\dots,d\}(因为 d−2k+1⩽2kd - 2^k + 1 \leqslant 2^k), 正是原限制的全部等式,不多不少。反向也成立:原限制蕴含这两条(它们是原限制的子集)。

分层并查集(逆用 ST 表)。 由上可知,只需要 O(log⁡n)O(\log n) 个分层的并查集: 第 kk 层刻画"以 ii 开头、长度 2k2^k 的区间"之间的相等关系,第 kk 层上只有 i∈[1, n−2k+1]i \in [1,\, n-2^k+1] 这些元素合法。加入限制时按上面的办法在第 kk 层合并两次, 每条限制变 O(log⁡n)O(\log n)(找 kk 是 O(1)O(1),只要预先知道 ⌊log⁡2L⌋\lfloor\log_2 L\rfloor)。

自顶向下下放(这一步就是"逆用 ST 表")。 现在关系都在高层,第 00 层还是散的。 从最高层 kmax⁡=⌊log⁡2n⌋k_{\max} = \lfloor\log_2 n\rfloor 往下扫到第 11 层,对每个合法起点 ii:

  1. 先取 p=findk(i)p = \text{find}_k(i),即与第 ii 个区间同属一个集合的代表元区间;
  2. 把"第 ii 个区间 == 第 pp 个区间"拆成两对更短的区间:
    [i,  i+2k−1−1]=[p,  p+2k−1−1],[i+2k−1,  i+2k−1]=[p+2k−1,  p+2k−1].\big[i,\;i+2^{k-1}-1\big] = \big[p,\;p+2^{k-1}-1\big], \qquad \big[i+2^{k-1},\;i+2^k-1\big] = \big[p+2^{k-1},\;p+2^k-1\big].

第 kk 层的每个集合里,所有区间两两相等,而每对"ii 与代表元 pp"的拆分结果已经把所有元素 锁定到 pp 的左右两半上,所以整个集合的相等关系被完整下放到第 k−1k-1 层; 同时 k−1k-1 层已有的关系不动。这一步的总量是 ∑k=1⌊log⁡2n⌋(n−2k+1)\sum_{k=1}^{\lfloor\log_2 n\rfloor} (n-2^k+1) 次查找 ≈ O(nlog⁡n)O(n\log n)。

统计答案。 全部下放完成后,第 00 层的并查集就是位置之间的最终相等关系。 数出连通块数 tt,套上面 9⋅10t−19 \cdot 10^{t-1} 的式子。

举一个最小的例子验证拆分的"重叠覆盖":n=6n=6,限制 1 3 4 6(L=3L = 3,k=1k = 1,2k=22^k = 2), 第一条窗口是 [1,2]=[4,5][1,2]=[4,5],第二条窗口是 [2,3]=[5,6][2,3]=[5,6]。 两条合起来的等式是 S1=S4,  S2=S5,  S3=S6S_1{=}S_4,\;S_2{=}S_5,\;S_3{=}S_6,正是 S[1..3] = S[4..6]。 题面给的例子 123123、351351 都满足它,131141 违反 S2=S5S_2 = S_5(3≠43 \neq 4)而被排除。

代码

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 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++ 版(同一算法):

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 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;
}

复杂度

  • 时间:每条限制 O(1)O(1) 次分层合并(合并本身 O(α)O(\alpha));下放阶段共 O(nlog⁡n)O(n\log n) 次查找与合并;统计 O(n α)O(n\,\alpha)。总计 O((n+m)log⁡n α(n))O((n + m)\log n\ \alpha(n))(α\alpha 为反阿克曼函数,实际近似常数)。 与朴素 O(nm)O(nm) 相比,在 n=m=105n = m = 10^5 时从 101010^{10} 降到约 1.7×1061.7 \times 10^6 次并查集操作。
  • 空间:C++ 版开 ⌊log⁡2n⌋+1\lfloor\log_2 n\rfloor + 1 层(n=105n = 10^5 时为 1717 层,数组上限取 1818), 每层两个长度为 n+1n+1 的 int 数组,约 2×17×105×4B≈13.62 \times 17 \times 10^5 \times 4\text{B} \approx 13.6 MB, 远低于 512 MB 限制;Python 版是 1717 个长度为 n+1n+1 的 list,常数大得多但同样可接受。
  • 实现细节:第 kk 层只需给 i∈[1,n−2k+1]i \in [1, n-2^k+1] 初始化,但我为省事把 1∼n1 \sim n 全初始化了,多出来的位置永远用不到、不影响正确性。 下放阶段加了一句 if (p == i) continue;:此时 ii 自己就是代表元,两对拆分都是自等, 合并它没有任何信息量,跳过可以省掉大量无用的 find。
  • 限时:题目限时 1000 ms。C++ 版实测在顶格点(n=m=105n=m=10^5)上远低于 100 ms; Python 版在同样的点上明显更慢,属于 Python 语言的常数问题,而非算法差异。

总结

  • 先化简模型,再谈数据结构:题面讲的是"大数字符串相等",但一旦把位置看成变量, 问题就只剩"哪些位置必须相同" —— 本质是等价类计数,与具体数字无关, 连"数有多少种取值"这件事都被压缩成了一个 9⋅10t−19 \cdot 10^{t-1} 的式子。
  • 能拆就能省:一段长等式可以无损劈成两段半长等式,这既是可拆分性、也是可替代性。 利用它把"长度 LL 的等式"换成"两段长度 2⌊log⁡2L⌋2^{\lfloor\log_2 L\rfloor} 的等式", 覆盖的正确性依赖于 2⋅2k⩾L2 \cdot 2^k \geqslant L,也就是两个窗口一定会重叠。
  • 逆用 ST 表:ST 表是"用两段短区间合成一段长区间",这里反过来 —— 先在高层(长区间)记账,再从高到低把账往下滚。分层编号 kk 与区间长度 2k2^k 绑定, 所以下放时不需要任何额外的区间长度信息,只靠层号就能定位拆分点。
  • 边界:n=1n = 1 时答案恒为 99(一位数 1∼91\sim9);mm 条限制全是自等 (如 i i i i)时不做任何合并,t=nt = n,答案 9⋅10n−19 \cdot 10^{n-1}; 同一对位置被多组限制重复约束时并查集自动去重,不需要特判。
  • 数据说明:本题素材自带数据生成脚本 data.py,data/ 是据此自造的 (共 10 个点,含 n=m=1n=m=1 的边界、可解析验证的结构点、以及 n=m=105n=m=10^5 的顶格随机点), 题面本身是从一本通《高手训练》重建的;经比对,本题与 [SCOI2016] 萌萌哒 (洛谷 P3295 / BZOJ 4569)完全同题,n,m⩽105n,m \leqslant 10^5 的范围也一致。 因此下的结论只保证对这份自造数据成立,不宣称等于官方原题数据。