Description
给你一个长度为 \(n\) ，可含前导零的大数，以及一个质数 \(p\) 。 \(m\) 次询问，每次询问你一个大数的子区间 \([l,r]\) ，求出子区间中有多少个子串为 \(p\) 的倍数。
\(1\leq n,m\leq 100000\)
Solution
记 \(a_i\) 为大数第 \(i\) 位上的数值。
注意到题目是要求 \[\sum_{i=l}^r\sum_{j=i}^r\left[\sum_{k=i}^ja_k\cdot 10^{j-k}\equiv 0\pmod{p}\right]\]
我们可以将其等价变形 \[\Rightarrow\sum_{i=l}^r\sum_{j=i}^r\left[10^j\sum_{k=i}^ja_k\cdot 10^{-k}\equiv 0\pmod{p}\right]\]
由于 \(p\) 是质数，同时在 \(p\neq 2\wedge p\neq 5\) 时， \(\nexists i,10^i\equiv 0\pmod{p}\) ；且对于 \(\forall i,10^{-i}\) 存在逆元。
所以我们先讨论 \(p\neq 2\wedge p\neq 5\) 的情况。
我们不妨记 \(sum_i=\sum\limits_{j=1}^ia_j\cdot10^{-j}\) 在模 \(p\) 意义下的结果。
原式等价于 \[\begin{aligned}\Rightarrow&\sum_{i=l}^r\sum_{j=i}^r\left[\sum_{k=i}^ja_k\cdot 10^{-k}\equiv 0\pmod{p}\right]\\=&\sum_{i=l}^r\sum_{j=i}^r\left[sum_j-sum_{i-1}\equiv 0\pmod{p}\right]\\=&\sum_{i=l}^r\sum_{j=i}^r\left[sum_j=sum_{i-1}\right]\end{aligned}\]
发现这不就是莫队的板子么，求子区间内有多少数对相等。直接套板子就好了。
然后对于 \(p= 2\vee p= 5\) ，可以特判，讨论比较简单，不再赘述。
Code
注意这个代码是过不了的。但在 luogu 上强行开 O2 过了，就得过且过吧...
但是可以有这些优化：
- 优化莫队的计算过程，不用每次都算一遍组合数；
- 不用写 \(hash\) 表，直接排序离散化就好了
//It is made by Awson on 2018.2.11
#include <bits/stdc++.h>
#define LL long long
#define dob complex<double>
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
#define writeln(x) (write(x), putchar('\n'))
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N = 200000;
const int MOD = 1e6+7;
void read(int &x) {
char ch; bool flag = 0;
for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
x *= 1-2*flag;
}
void print(LL x) {if (x > 9) print(x/10); putchar(x%10+48); }
void write(LL x) {if (x < 0) putchar('-'); print(Abs(x)); }
int p, n, m, sum[N+5], inv, lim;
int tol[MOD+5];
char num[N+5];
LL ans[N+5];
namespace cheat2 {
struct bittree {
LL c[N+5];
void add(int x, int val) {for (; x <= n; x += lowbit(x)) c[x] += val; }
LL query(int x) {
LL sum = 0;
for (; x; x -= lowbit(x)) sum += c[x];
return sum;
}
}T;
int sum[N+5];
void main() {
scanf("%s", num+1); n = strlen(num+1);
for (int i = 1; i <= n; i++)
if ((num[i]-48)%2 == 0) T.add(i, i), sum[i] = sum[i-1]+1;
else sum[i] = sum[i-1];
read(m); int l, r;
while (m--) {
read(l), read(r); writeln(T.query(r)-T.query(l-1)-1ll*(sum[r]-sum[l-1])*(l-1));
}
}
}
namespace cheat5 {
struct bittree {
LL c[N+5];
void add(int x, int val) {for (; x <= n; x += lowbit(x)) c[x] += val; }
LL query(int x) {
LL sum = 0;
for (; x; x -= lowbit(x)) sum += c[x];
return sum;
}
}T;
int sum[N+5];
void main() {
scanf("%s", num+1); n = strlen(num+1);
for (int i = 1; i <= n; i++)
if ((num[i]-48)%5 == 0) T.add(i, i), sum[i] = sum[i-1]+1;
else sum[i] = sum[i-1];
read(m); int l, r;
while (m--) {
read(l), read(r); writeln(T.query(r)-T.query(l-1)-1ll*(sum[r]-sum[l-1])*(l-1));
}
}
}
struct HASH {
int k[MOD+5];
void clear() {memset(k, -1, sizeof(k)); }
void insert(int x) {
int loc = x%MOD;
while (true) {
if (k[loc] == -1 || k[loc] == x) {k[loc] = x; return; }
++loc; if (loc >= MOD) loc %= MOD;
}
}
int query(int x) {
int loc = x%MOD;
while (true) {
if (k[loc] == x) {return loc; }
++loc; if (loc >= MOD) loc %= MOD;
}
}
}mp;
struct tt {
int l, r, id;
bool operator < (const tt &b) const {return l/lim == b.l/lim ? r < b.r : l < b.l; }
}a[N+5];
int quick_pow(int a, int b, int p) {
int ans = 1;
while (b) {
if (b&1) ans = 1ll*ans*a%p;
b >>= 1, a = 1ll*a*a%p;
}
return ans;
}
LL C(int n) {return 1ll*n*(n-1)/2;}
void work() {
read(p); mp.clear();
if (p == 2) {cheat2::main(); return; }
if (p == 5) {cheat5::main(); return; }
inv = quick_pow(10, p-2, p); scanf("%s", num+1); n = strlen(num+1); lim = sqrt(n);
mp.insert(0);
for (int i = 1, j = inv; i <= n; i++, j = 1ll*j*inv%p) {
sum[i] = (sum[i-1]+1ll*(num[i]-48)*j%p)%p;
mp.insert(sum[i]);
}
read(m);
for (int i = 1; i <= m; i++) {read(a[i].l), --a[i].l, read(a[i].r), a[i].id = i; }
sort(a+1, a+m+1);
LL now = 0; int curl = 0, curr = 0; tol[mp.query(0)] = 1;
for (int i = 1; i <= m; i++) {
int l = a[i].l, r = a[i].r;
int id = mp.query(sum[curl]);
while (curl < l) now -= C(tol[id]), --tol[id], now += C(tol[id]), ++curl, id = mp.query(sum[curl]);
id = mp.query(sum[curl-1]);
while (curl > l) --curl, now -= C(tol[id]), ++tol[id], now += C(tol[id]), id = mp.query(sum[curl-1]);
id = mp.query(sum[curr+1]);
while (curr < r) ++curr, now -= C(tol[id]), ++tol[id], now += C(tol[id]), id = mp.query(sum[curr+1]);
id = mp.query(sum[curr]);
while (curr > r) now -= C(tol[id]), --tol[id], now += C(tol[id]), --curr, id = mp.query(sum[curr]);
ans[a[i].id] = now;
}
for (int i = 1; i <= m; i++) writeln(ans[i]);
}
int main() {
work(); return 0;
}