LibreOJ 2014 「SCOI2016」萌萌哒

发表于 | 分类于

Description

有一个长度为\(n\)的无前导零数字串。

现在给你\(m\)组信息，形如\((a,b,c,d)\)（保证\(a\leq b, c\leq d,b - a = d - c\)），表示数字串\(a\ldots b\)这一段子串和\(c\ldots d\)这一段子串是一样的。

求最后的数字串有多少种可能。

\(1\leq n, m\leq 10^5, 1\leq a,b,c,d\leq n\)。

Solution

ao劲啊这种题，，，

肯定要上并查集辣……但是暴力建图一定会炸，线段树优化建图在这也不好用（两边子树的形态可能差异巨大）。那么考虑用倍增优化建图。

建出形如\(v(i, j)\)的点表示从\(i\)开始长度为\(2^j\)的子串。然后这样用类似于ST表的方式就可以处理所有信息了，具体方式就是把对应的两组点在并查集上连一下。

然后考虑最后如何统计答案。这个也不难，你把并查集的关系逐层往下推就行。

Code

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
const int maxn = 100005;
const int maxs = maxn * 17;

using ll = long long;
const ll ha = 1000000007LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1LL, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}

int p[maxs], rk[maxs];
void init_set(int s) {
  for(int i = 1; i <= s; i ++) {
    p[i] = i; rk[i] = 0;
  }
}
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return (p[x] = get_fa(p[x]));
  }
}
void link_set(int x, int y) {
  if(rk[x] > rk[y]) std::swap(x, y);
  p[x] = y; if(rk[x] == rk[y]) rk[y] ++;
}
void merge_set(int x, int y) {
  x = get_fa(x); y = get_fa(y);
  if(x != y) link_set(x, y);
}

int n, cnt;
int lst[maxn];
int num[maxn][17], lc[maxs], rc[maxs];
void process() {
  lst[1] = 0;
  for(int i = 2; i <= n; i ++) {
    lst[i] = lst[i - 1];
    while((1 << (lst[i] + 1)) <= i) lst[i] ++;
  }
  cnt = 0;
  for(int j = 0; (1 << j) <= n; j ++) {
    for(int i = 1; i + (1 << j) - 1 <= n; i ++) {
      num[i][j] = ++ cnt;
      if(j > 0) {
        lc[cnt] = num[i][j - 1];
        rc[cnt] = num[i + (1 << (j - 1))][j - 1];
      }
    }
  }
  init_set(cnt);
}
void update(int a, int b, int c, int d) {
  int g = lst[b - a + 1];
#ifdef LOCAL
  printf("Operation (%d, %d, %d, %d) %d\n", a, b, c, d, g);
#endif
  merge_set(num[a][g], num[c][g]);
  merge_set(num[b - (1 << g) + 1][g], num[d - (1 << g) + 1][g]);
}

int main() {
  int m; scanf("%d%d", &n, &m);
  process();
  while(m --) {
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    update(a, b, c, d);
  }
  for(int i = cnt; i > n; i --) {
    int fa = get_fa(i);
    merge_set(lc[i], lc[fa]);
    merge_set(rc[i], rc[fa]);
  }
  int blk = 0;
  for(int i = 1; i <= n; i ++) {
    if(get_fa(i) == i) blk ++;
  }
  ll ans = 9LL * pow_mod(10LL, blk - 1) % ha;
  printf("%lld\n", ans);
  return 0;
}