Description
Description
一个长度为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,后者第二位与第五位不同。问满足以上所有条件的数有多少个。
Input
第一行两个数n和m,分别表示大数的长度,以及限制条件的个数。接下来m行,对于第i行,有4个数li1,ri1,li2,ri2,分别表示该限制条件对应的两个区间。
1≤n≤10^5,1≤m≤10^5,1≤li1,ri1,li2,ri2≤n;并且保证ri1-li1=ri2-li2。
Output
一个数,表示满足所有条件且长度为n的大数的个数,答案可能很大,因此输出答案模10^9+7的结果即可。
Sample Input
4 2
1 2 3 4
3 3 3 3
Sample Output
90
题解思路 先设一个数组f[i][j],表示从i个数开始向后2的j次方个数与从f[i][j]个数开始向后2的j次方个数相同。对于每两个相等的区间,我们先用倍增将它们划分为多个长度2的次方个小段,再将每一个小段以并查集的方式合并。 这个操作的时间复杂度是O(nlogn)。 然后从2的最大次方开始,若f[i][j]=k,则将其转换为合并f[i][j-1],k以及f[i+2^(j-1)][j],k。 这个操作的时间复杂度也是O(nlogn)的。 最后统计一个s,表示f[i][0]=i的i的个数。 最后用快速幂求出9*(10^(s-1))即可(开头不能为0)(其实龟速乘也可以) 这个的时间复杂度是O(n)的。 所以总的时间复杂度是O(nlogn)
#include<iostream> #include<cstdio> using namespace std; long long n,m,l1,l2,r1,r2,f[100001][21],v[21],cnt=-1,fx,fy,s,ans=1,mod=1000000007; long long fa(long long id,long long a){ if(f[a][id]!=a)f[a][id]=fa(id,f[a][id]); return f[a][id]; } long long find(long long a){ s=10ll; while(a>0){ if(a%2ll)ans=(ans*s)%mod; s=(s*s)%mod; a=a/2ll; } } void merge(long long id,long long x,long long y){ fx=fa(id,x); fy=fa(id,y); if(fx!=fy)f[fx][id]=fy; } int main(){ v[0]=1; for(long long i=1;i<=20;i++)v[i]=v[i-1]*2; scanf("%lld%lld",&n,&m); for(long long i=1;i<=n;i++)for(long long j=0;j<=20;j++)f[i][j]=i; for(long long i=1;i<=m;i++){ scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2); for(long long j=20;j>=0;j--){ if(v[j]<=r1-l1+1){ merge(j,l1,l2); l1=l1+v[j]; l2=l2+v[j]; } } } for(long long i=20;i;i--){ for(long long x=1;x+v[i]-1<=n;x++){ s=fa(i,x); merge(i-1,x,s); merge(i-1,x+v[i-1],s+v[i-1]); } } for(long long i=1;i<=n;i++){ s=fa(0,i); if(s==i)cnt++; } find(cnt); ans=ans*9ll; ans=ans%mod; printf("%lld\n",ans); }