思路与算法

第k层并查集表示长度2^k的子串完全相等。任意等长约束用不短于一半的首块和尾块覆盖整个区间，分别合并；从高层向低层，每个块与同类代表合并它们的左右半块。最终第0层就是位置相等关系，若有c类，首位所在类9种选择，其余每类10种，答案9×10^(c-1)。

正确性说明

首尾块并集覆盖整个区间，不引入区间外位置，因此该两次合并与原等长限制等价。高层相等必然推出对应半块相等，逐层传播直到单字符，无额外关系也无遗漏。各等价类独立取数字，唯首位不能0。

复杂度

初始化全部层O(NlogN)，每条约束常数次合并，向下传播O(NlogN)次并查集操作。本实现仅做路径压缩、不按秩合并，按保守摊还O(logN)计，总O((M+NlogN)logN)时间；空间O(NlogN)。最终类计数和乘幂循环O(N)。

易错点

块起点不能让整块越界。约束可自等和重叠；首位禁0约束属于整个等价类，不是只对一个位置单独扣除。 并查集查找采用迭代路径压缩，避免等价类长链使原生栈溢出；不缩小10万规模。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int main() {
    int n, m;
    cin >> n >> m;
    int K = 0;
    while ((1 << (K + 1)) <= n)
        K++;
    vector<vector<int>> p(K + 1, vector<int>(n));
    for (auto &v : p)
        iota(v.begin(), v.end(), 0);
    function<int(int, int)> find = [&](int k, int x) {
        int root = x;
        while (p[k][root] != root)
            root = p[k][root];
        while (p[k][x] != x) {
            int next = p[k][x];
            p[k][x] = root;
            x = next;
        }
        return root;
    };
    auto join = [&](int k, int a, int b) {
        a = find(k, a);
        b = find(k, b);
        if (a != b)
            p[k][a] = b;
    };
    while (m--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        --a;
        --c;
        int len = b - a, k = 31 - __builtin_clz(len);
        join(k, a, c);
        join(k, b - (1 << k), d - (1 << k));
    }
    for (int k = K; k > 0; k--)
        for (int i = 0; i + (1 << k) <= n; i++) {
            int j = find(k, i);
            join(k - 1, i, j);
            join(k - 1, i + (1 << (k - 1)), j + (1 << (k - 1)));
        }
    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (find(0, i) == i)
            cnt++;
    long long ans = 9;
    for (int i = 1; i < cnt; i++)
        ans = ans * 10 % MOD;
    cout << ans << '\n';
}