Description
Input
Output
Sample Input
4 2
1 2 3 4
3 3 3 3
Sample Output
90
Data Constraint
\
Solution
暴力：直接并查集，找联通块个数，时间复杂度O(nm)。
正解：设f[ i ][ j ]表示第i个点开始的连续的2^j个数对应着与其相同的区间的开头。即f[ i ][ j ]=k,则 i ~ i+2^j-1 与 k ~ k+2^j-1 相同。
每次将f[ i ][ j ]分成两段下传下去，直到覆盖整个区间。时间复杂度 O(n long n)。为什么？因为最多有n long n 个区间，我们每次将两个区间合并，而如果两个区间在并查集中的父亲已经相等则退出，所以最多只需要合并n long n 次。
Code1
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 100010
#define ll long long
#define M 1000000007
using namespace std;
int n,m,l1,r1,l2,r2,tot;
int f[N][22];
ll ans;
ll ksm(ll x,int k){
if(!k) return 1;
if(k==1) return x%M;
ll s=ksm(x,k/2);s=(s*s)%M;
if(k%2==0) return s;
return (s*x)%M;
}
int get(int x,int k){
if(f[x][k]==x) return x;
return f[x][k]=get(f[x][k],k);
}
void find(int x,int y,int k){
int fx=get(x,k),fy=get(y,k);
if(fx==fy) return;
f[fx][k]=fy;
if(!k) return;
find(x,y,k-1);find(x+(1<<(k-1)),y+(1<<(k-1)),k-1);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=0;j<=19;j++) f[i][j]=i;
}
while(m--){
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
int k=log2(r1-l1+1);
find(l1,l2,k);
find(r1-(1<<k)+1,r2-(1<<k)+1,k);
}
for(int i=1;i<=n;i++) tot+=(get(i,0)==i);
ans=(ksm(10,tot-1)*9)%M;
printf("%lld\n",ans);
return 0;
}
Code2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 100010
#define ll long long
#define M 1000000007
using namespace std;
int n,m,l1,r1,l2,r2,tot;
int f[N][22];
ll ans;
ll ksm(ll x,int k){
if(!k) return 1;
if(k==1) return x%M;
ll s=ksm(x,k/2);s=(s*s)%M;
if(k%2==0) return s;
return (s*x)%M;
}
int get(int x,int k){
if(f[x][k]==x) return x;
return f[x][k]=get(f[x][k],k);
}
void merge(int x,int y,int k1,int k2){
int fx=get(x,k1),fy=get(y,k2);
if(fx!=fy) f[fx][k1]=fy;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=0;j<=19;j++) f[i][j]=i;
}
while(m--){
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
int k=log2(r1-l1+1);
merge(l1,l2,k,k);
merge(r1-(1<<k)+1,r2-(1<<k)+1,k,k);
}
for(int j=18;j>0;j--){
for(int i=1;i<=n;i++){
if(f[i][j]==i) continue;
merge(i,f[i][j],j-1,j-1);
merge(i+(1<<(j-1)),f[i][j]+(1<<(j-1)),j-1,j-1);
}
}
for(int i=1;i<=n;i++) tot+=(get(i,0)==i);
ans=(ksm(10,tot-1)*9)%M;
printf("%lld\n",ans);
return 0;
}
作者：zsjzliziyang QQ:1634151125 转载及修改请注明 本文地址:https://blog.csdn.net/zsjzliziyang/article/details/90452375
