题目
一个长度为\(n\)的串,有\(m\)个限制条件,\(l_1,r_1,l_2,r_2(r_1-l_1=r_2-l_2)\)表示,字串\([l_1,r_1]\)和字串\(l_2,r_2\)相等.你可以在除最高位的每一位填0123456789,最高位不能为0,问方案.
\(n,m\le 10^5\)
思路
容易将问题转化为求字符串中不同的字符数量.
用并查集维护,用类似st表的方式优化.
我们设字符串中起始位置为\(i\),长度为\(2^j\)的字符串编号为\(st_{i,j}\).它所在的集合为\(fa_{st_{i,j}}\).在同一个集合的字符串相等.
对于限制条件,我们可以二进制拆分原来的字符串,在并查集上维护.
处理完限制条件后,我们需要将相等关系下传,得到长度为1的字串的相等关系,从而解决这道题.
具体地说我们枚举一个以\(i\)为起点,长度为\(2^j\)的字符串,把它分成两半:起点为\(i\),长度为\(2^{j-1}\),以及起点为\(i+2^{j-1}\),长度为\(2^{j-1}\).我们在并查集中找到原串的相同串,设它的起始位置为\(id\),(这一步可能需要一个额外的数组维护),也将它分为两半,起点为\(id\),长度为\(2^{j-1}\),以及起点为\(id+2^{j-1}\),长度为\(2^{j-1}\).
可以得到两组相同串:起点为\(i\),长度为\(2^{j-1}\)的串和起点为\(id\),长度为\(2^{j-1}\)的串,起点为\(i+2^{j-1}\),长度为\(2^{j-1}\)的串和起点为\(id+2^{j-1}\),长度为\(2^{j-1}\)的串,将它们在并查集上么并即可.
代码
#include <iostream>
#include <cstdio>
#include <unordered_set>
using namespace std;
int read() {
int re = 0;
char c = getchar();
bool negt = false;
while(c < '0' || c > '9')negt |= (c == '-') , c = getchar();
while(c >= '0' && c <= '9')re = (re << 1) + (re << 3) + c - '0' , c = getchar();
return negt ? -re : re;
}
const int N = 1e5 + 10 , logN = 20;
struct DSU {
int fa[N * logN];
void init(int n) {
for(int i = 1 ; i <= n ; i++)
fa[i] = i;
}
int findroot(int x) {
return fa[x] == x ? x : (fa[x] = findroot(fa[x]));
}
void merge(int x , int y) {
if(findroot(x) != findroot(y))
fa[findroot(x)] = findroot(y);
}
} dsu;
int n , m;
int st[N][logN];
int indx[N * logN];//编号为i的串,起始位置为indx[i].
int log2[N];
unordered_set<int> s;
void init() {
int cnt = 0;//编号
for(int j = 0 ; (1 << j) <= n ; j++)
for(int i = 1 ; i + (1 << j) - 1 <= n ; i++)
st[i][j] = ++cnt , indx[cnt] = i;
for(int i = 2 ; i <= n ; i++)
log2[i] = log2[i - 1] + ((i & i - 1) == 0);
dsu.init(cnt);
}
typedef long long ll;
ll mod = 1e9 + 7;
int poww(ll mul , int p) {
int ans = 1;
for( ; p ; p >>= 1)ans = (ans * ((p & 1) ? mul : 1)) % mod , mul = mul * mul % mod;
return ans;
}
int main() {
n = read() , m = read();
init();
for(int i = 1 ; i <= m ; i++) {
int l1 = read() , r1 = read() , l2 = read() , r2 = read();
int len = r1 - l1 + 1;
int p = l1 , q = l2;
for(int j = log2[len] ; j >= 0 ; j--) {
if(p + (1 << j) - 1 > r1)continue;
dsu.merge(st[p][j] , st[q][j]);
p += (1 << j) , q += (1 << j);
}
}
for(int j = log2[n] + 1 ; j > 0 ; j--) {
for(int i = 1 ; i + (1 << j) - 1 <= n ; i++) {
int id = indx[dsu.findroot(st[i][j])];
dsu.merge(st[i][j - 1] , st[id][j - 1]);
dsu.merge(st[i + (1 << j - 1)][j - 1] , st[id + (1 << j - 1)][j - 1]);
}
}
for(int i = 1 ; i <= n ; i++)
s.insert(dsu.findroot(i));
printf("%lld" , 9ll * poww(10 , s.size() - 1) % mod);
// cout << s.size();
return 0;
}