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
#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);
}
xsy 2412【BZOJ4569】【Scoi2016】萌萌哒
原文：https://www.cnblogs.com/ez-syh/p/11615488.html