挖掘性质变莫队.

Description

给一个数字串$S$和模数$p$, 有若干询问, 每次问$S$的$[l,r]$的所有子串有多少$\mod P = 0$.

Solution

观察到对于一个$[l, r]$串, 如果$[r+1, n] \equiv [l,n] (\mod P)$, 那么这个区间就可以被$P$整除, 2和5除外, 这两种情况只要末尾整除就可以, 特判掉就好了.

我们发现相邻位置是可以$O(1)$增量更新的, 所以可以莫队.

模数很大, 但情况不多, 需要离散化.

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e+5 + 5;

int n, m, bel[maxn], rem[maxn], cpy[maxn], cnt, p, bkt[maxn];
int blo;
ll ans[maxn], pts[maxn], lns[maxn];
char str[maxn];
struct query {
  int l, r, id;
  inline bool operator < (const query &rhs) const {
    return bel[l] == bel[rhs.l] ? 
            r < rhs.r : bel[l] < bel[rhs.l];
  }
}q[maxn];

int main() {
  scanf("%d", &p);
  scanf("%s", str + 1);
  scanf("%d", &m);
  n = strlen(str + 1); blo = sqrt(n + 1);
  for (int i = 1; i <= n + 1; ++i) 
    bel[i] = (i - 1) / blo + 1;
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i;
  }
  if (p != 2 && p != 5) {
    ll base = 1;
    for (int i = n; i; --i) {
      base = base * 10 % p;
      rem[i] = (rem[i + 1] + (str[i] ^ 48) * base) % p;
      cpy[i] = rem[i];
    }
    cpy[n + 1] = 0;
    sort(cpy + 1, cpy + 2 + n);
    cnt = unique(cpy + 1, cpy + 2 + n) - (cpy + 1);
    for (int i = 1; i <= n + 1; ++i)
      rem[i] = lower_bound(cpy + 1, cpy + 1 + cnt, rem[i]) - cpy;

    for (int i = 1; i <= m; ++i) q[i].r++;
    sort(q + 1, q + 1 + m);
    ll l = 1, r = 0, cur = 0;

    for (int i = 1; i <= m; ++i) {
      while (r < q[i].r) {cur += bkt[rem[++r]]; bkt[rem[r]]++;}
      while (l > q[i].l) {cur += bkt[rem[--l]]; bkt[rem[l]]++;}
      while (r > q[i].r) {bkt[rem[r]]--; cur -= bkt[rem[r--]];}
      while (l < q[i].l) {bkt[rem[l]]--; cur -= bkt[rem[l++]];}
      ans[q[i].id] = cur;
    }
    for (int i = 1; i <= m; ++i)
      printf("%lld\n", ans[i]);
  } else {
    for (int i = 1; i <= n; ++i) {
      if (!((str[i] ^ 48) % p)) 
        pts[i] = pts[i - 1] + 1, lns[i] = lns[i - 1] + i;
      else 
        pts[i] = pts[i - 1], lns[i] = lns[i - 1];
    }
    int l, r;
    for (int i = 1; i <= m; ++i) {
      //scanf("%d%d", &l, &r);
      l = q[i].l; r = q[i].r;
      printf("%lld\n", lns[r] - lns[l - 1] - (pts[r] - pts[l - 1]) * (l - 1));
    }
  }

  return 0;
}