题目链接
解析
莫队
设\(num_i\)表示\(s[1…n]\)所表示的数
那么\(s[l…r]\)表示的数为\(\frac{num_l - num_{r + 1}}{10^{n - r}}\)
所以题目即求满足\(\frac{num_l - num_{r + 1}}{10^{n - r}} \equiv 0 \ (mod \ p)\)的\((l, r)\)对数
- 当\(p \neq 2, p \ne 5\)时，\(p\)和\(10\)互质，上式可化为\(num_l \equiv num_{r + 1} \ (mod \ p)\)，问题变成了统计区间相同数个数，上莫队就行了（当然要离散化余数）
- 当\(p = 2\)或\(p = 5\)时，末位数字有规律，可以继续莫队，或者前缀和搞一搞
一个注意的地方：离散化的时候把\(n+1\)位置一起离散……
代码
#include#include #include #include #define MAXN 100010typedef long long LL;struct Query { int l, r, id, blk; bool operator <(const Query &q) const;};void prework();void work1();void work2();void work3();int N, M, P, perblock, num[MAXN], vec[MAXN];LL pow10[MAXN], f[MAXN], g[MAXN];char s[MAXN];Query qry[MAXN];int main() { scanf("%d%s%d", &P, s + 1, &M); N = strlen(s + 1); if (P == 2) work1(); else if (P == 5) work2(); else work3(); return 0;}bool Query::operator <(const Query &q) const { return blk == q.blk ? r < q.r : blk < q.blk; }void work1() { for (int i = 1; i <= N; ++i) { f[i] = f[i - 1], g[i] = g[i - 1]; if (((s[i] - '0') & 1) ^ 1) f[i] = f[i] + i, ++g[i]; } while (M--) { int l, r; scanf("%d%d", &l, &r); printf("%lld\n", f[r] - f[l - 1] - (l - 1) * (g[r] - g[l - 1])); }}void work2() { for (int i = 1; i <= N; ++i) { f[i] = f[i - 1], g[i] = g[i - 1]; if (s[i] == '0' || s[i] == '5') f[i] = f[i] + i, ++g[i]; } while (M--) { int l, r; scanf("%d%d", &l, &r); printf("%lld\n", f[r] - f[l - 1] - (l - 1) * (g[r] - g[l - 1])); } }void prework() { while (perblock * perblock <= N) ++perblock; pow10[0] = 1; for (int i = 1; i <= N; ++i) pow10[i] = pow10[i - 1] * 10 % P; for (int i = N; i; --i) num[i] = ((LL)num[i + 1] + (s[i] - '0') * pow10[N - i] % P) % P; for (int i = 1; i <= N; ++i) vec[i - 1] = num[i]; std::sort(vec, vec + N + 1);//注意要把N+1位置的0一起离散化 int tot = std::unique(vec, vec + N + 1) - vec; for (int i = 1; i <= N + 1; ++i) num[i] = std::lower_bound(vec, vec + tot, num[i]) - vec; for (int i = 0; i < M; ++i) { scanf("%d%d", &qry[i].l, &qry[i].r); qry[i].id = i; ++qry[i].r; qry[i].blk = (qry[i].l - 1) / perblock; } std::sort(qry, qry + M);}void work3() { prework(); LL cur = 0; for (int i = 0, l = 1, r = 0; i < M; ++i) { while (r < qry[i].r) ++r, cur += g[num[r]], ++g[num[r]]; while (l > qry[i].l) --l, cur += g[num[l]], ++g[num[l]]; while (r > qry[i].r) --g[num[r]], cur -= g[num[r]], --r; while (l < qry[i].l) --g[num[l]], cur -= g[num[l]], ++l; f[qry[i].id] = cur; } for (int i = 0; i < M; ++i) printf("%lld\n", f[i]);}//Rhein_E