题目大意
一个长度为$n$的大数，用$S_1S_2S_3\cdots S_n$表示，其中$S_i$表示数的第$i$位,$S_1$是数的最高位，告诉你一些限制条件，每个条件表示为四个数，$l_1,r_1,l_2,r_2$，即两个长度相同的区间，表示子串$S_{l_1}S_{l_1+1}S_{l_1+2}\cdots S_{r_1}$与$S_{l_2}S_{l_2+1}S_{l_2+2}\cdots S_{r_2}$完全相同。比如$n=6$时，某限制条件$l_1=1,r_1=3$，$l_2=4,r_2=6$，那么$123123,351351$均满足条件，但是$12012,131141$不满足条件，前者数的长度不为$6$，后者第二位与第五位不同。问满足以上所有条件的数有多少个。
题目分析
首先考虑暴力，建立并查集，把对应的相同元素合并起来，最后统计集合个数$num$，$9\cdot10^{num-1}$即为答案。
时间复杂度$O(nm)$。
接下来开始表演。
不妨使用ST表优化暴力合并的过程，建$\log n$个并查集，每个并查集表示位置后$2^i$个元素对应相等。
这样在合并的时候只需要$O(1)$即可完成。
在限制条件处理完后需要对这$\log n$个并查集进行合并（下传）。
ST表从大到小枚举并查集中的每个点，将这个点的集合合并到后一个并查集对应的集合中。
时间复杂度$O(m+n\log n)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005,maxl=20,mod=1e9+7;
struct Union_Set {
int father[maxn];
void init(int n) {
for(int i=1; i<=n; i++)father[i]=i;
}
int Get_Father(int x) {
if(father[x]==x)return x;
return father[x]=Get_Father(father[x]);
}
int merge(int x,int y) {
int fx=Get_Father(x),fy=Get_Father(y);
if(fx!=fy)father[fx]=fy;
}
} set[maxl];
LL Quick_Pow(LL a,LL b) {
LL ans=1;
for(; b; b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
return ans;
}
int n,m,Log[maxn];
int main() {
n=Get_Int();
for(int i=2; i<=n; i++)Log[i]=Log[i>>1]+1;
for(int i=0; i<=Log[n]; i++)set[i].init(n);
m=Get_Int();
while(m--) {
int x=Get_Int(),y=Get_Int(),l=Get_Int(),r=Get_Int();
int len=r-l+1,d=Log[len];
set[d].merge(x,l);
set[d].merge(y-(1<<d)+1,r-(1<<d)+1);
}
for(int j=Log[n]; j>=1; j--)
for(int i=1; i+(1<<j)-1<=n; i++) {
int pos=set[j].Get_Father(i);
set[j-1].merge(i,pos);
set[j-1].merge(i+(1<<(j-1)),pos+(1<<(j-1)));
}
int cnt=0;
for(int i=1; i<=n; i++)cnt+=set[0].Get_Father(i)==i;
printf("%d\n",9ll*Quick_Pow(10,cnt-1)%mod);
return 0;
}
|
