首页 > 代码库 > 四川oi 萌萌哒 （分层并查集）

四川oi 萌萌哒 （分层并查集）

2024-11-19 00:26:04   203人阅读

 萌萌哒

时间限制: 1 Sec  内存限制: 256 MB
提交: 12  解决: 2
[提交][状态][讨论版]

题目描述

一个长度为 n 的大数，用 S1S2S3...Sn表示，其中 Si表示数的第 i 位, S1是数的最高位，告诉你一些限制条件，每个条件表示为四个数，l1, r1, l2, r2，即两个长度相同的区间，表示子串 Sl1Sl1+1Sl1+2...Sr1与 Sl2Sl2+1Sl2+2...Sr2完全相同。
比如 n = 6 时，某限制条件 l1= 1, r1= 3, l2 = 4, r2 = 6，那么 123123, 351351 均满足条件，但是 12012, 131141不满足条件，前者数的长度不为 6，后者第二位与第五位不同。
问满足以上所有条件的数有多少个

输入

第一行两个数 n 和 m，分别表示大数的长度，以及限制条件的个数
接下来 m 行，对于第 i 行, 有 4 个数 li1, ri1, li2, ri2，分别表示该限制条件对应的两个区间

输出

一个数，表示满足所有条件且长度为 n 的大数的个数，答案可能很大，因此输出答案模 109+7 的结果即可

样例输入

4 21 2 3 43 3 3 3

样例输出

90

提示

100% 的数据，1 ≤ n ≤ 105, 1 ≤ m ≤ 105, 1 ≤ li1, ri1, li2, ri2≤ n，并且保证 ri1− li1= ri2− li2

【分析】暴力并查集合并肯定超时，考虑倍增的思想，将并查集分层，fa[k][x]表示从x开始的长度为2^k的合并，然后 高位到低位合并即可。

  

#include <bits/stdc++.h>#define inf 0x3f3f3f3f#define met(a,b) memset(a,b,sizeof a)#define pb push_back#define mp make_pair#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;const int N = 1e6+5500;;const int M = 160009;const int mod = 1e9+7;const double pi= acos(-1.0);typedef pair<int,int>pii;int n,m,T;int up[N],go[N],fa[20][N];int findfa(int k,int x){    return x==fa[k][x]?x:fa[k][x]=findfa(k,fa[k][x]);}void unionfa(int k,int x,int y){    int X = x,Y = y;    x=findfa(k,x);    y=findfa(k,y);    if(x==y)return;    fa[k][x]=y;    if(!k)return;    unionfa(k-1,X,Y);    unionfa(k-1,X+(1<<k-1),Y+(1<<k-1));}int main(){    scanf("%d%d",&n,&m);    for(int j=0;j<20;j++)for(int i=0;i<N;i++)fa[j][i]=i;    for(int i=0,l1,r1,l2,r2;i<m;i++){        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);        if(l1>l2){            swap(l1,l2);swap(r1,r2);        }        int k=log2(r1-l1+1);        unionfa(k,l1,l2);unionfa(k,r1-(1<<k)+1,r2-(1<<k)+1);    }    int cnt=0;    ll ans=9;    for(int i=1;i<=n;i++){        if(findfa(0,i)==i)cnt++;    }    for(int i=0;i<cnt-1;i++){        ans=ans*10%mod;    }    if(n==1)puts("10");    else printf("%lld\n",ans);    return 0;}

 

四川oi 萌萌哒 （分层并查集）


联系
我们