Problem

https://www.luogu.org/problemnew/show/P3295

Solution

很有趣

考虑如果两个数必须相同就并查集合并，若最终块个数 $cnt$ ，则答案为 $9\cdot 10^{cnt-1}$ 。

考虑对合并过程进行优化，即进行一个 ST 表的合并过程。

则每次操作都有 $\log n$ 对点合并。最后维护一个 ST 表的下放过程。即若 $f[i][j]$ 的父亲是 $X$，那么合并 $f[i][j-1]$ 与 $X$，合并 $f[i+2^{j-1}][j-1]$ 与 $X+2^{j-1}$。

#include<bits/stdc++.h>
#define MOD (1000000007ll)
using namespace std;
typedef long long ll;

const int N=1e5+10, OP=20;
int fa[N][OP];
int Find(int x, int y) { return fa[x][y]?fa[x][y]=Find(fa[x][y], y):x; }
bool Union(int a, int b, int c) {
    int af=Find(a, c), bf=Find(b, c);
    if(af==bf) return false;
    return fa[af][c]=bf;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin>>n>>m;
    int l1, r1, l2, r2, len;
    for(int i=1;i<=m;i++) {
        cin>>l1>>r1>>l2>>r2;
        len=r1-l1+1;
        for(int j=OP-1;j>=0;j--) if(len>=(1<<j))
            len-=1<<j, Union(l1, l2, j), l1+=1<<j, l2+=1<<j;
    }
    for(int j=OP-1;j>0;j--) 
        for(int i=1;i+(1<<j)-1<=n;i++)
            Union(i, Find(i, j), j-1), Union(i+(1<<j-1), Find(i, j)+(1<<j-1), j-1);
    int ans=0;
    ll tot=1;
    for(int i=1;i<=n;i++) ans+=!fa[i][0];
    for(int i=1;i<ans;i++) tot=tot*10%MOD;
    printf("%lld\n", tot*9%MOD);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3295.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆