【LG3245】[HNOI2016]大数

题面

洛谷

题解

60pts

拿vector记一下对于以每个位置为右端点符合要求子串的左端点，

则每次对于一个询问，扫一遍右端点在vector里面二分即可，

虽然空间是平方级别的但是因为数据水还是可以过60的

100pts

记\([i,n]\)表示的数为\(num_i\)，则一段区间\([l,r]\)所表示的数为

题目就要使\(\frac {num_l-num_{r+1}}{10^{r-l+1}}\% P=0\)

当\(gcd(10^{r-l+1},P)=1\)时，我们用将每一个\(num\% P\)离散化后莫队维护一下一个值出现的次数即可，

那么对于\(gcd(10^{r-l+1},P)\neq 1\)，可以知道此时\(P=2\)或\(5\)，因为这时候整除关系只与数的最后一位有关，

转移也非常显然。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int MAX_N = 1e5 + 5;

const int LEN = 320;

char a[MAX_N];

int N, P, Q, bel[MAX_N];

struct Query { int l, r, id; } q[MAX_N];

bool operator < (const Query &lhs, const Query &rhs) {

	if (bel[lhs.l] ^ bel[rhs.l]) return bel[lhs.l] < bel[rhs.l];

	else return (bel[lhs.l] & 1) ? lhs.r < rhs.r : lhs.r > rhs.r;

}

int s[MAX_N], h[MAX_N], pw[MAX_N];

long long Ans, Cnt, bln[MAX_N], ans[MAX_N];

void Ins(int x) { Ans += bln[s[x]], ++bln[s[x]]; }

void Ers(int x) { --bln[s[x]], Ans -= bln[s[x]]; }

void insl(int x) { Cnt += (a[x] - '0') % P == 0, Ans += Cnt; }

void dell(int x) { Ans -= Cnt, Cnt -= (a[x] - '0') % P == 0; }

void insr(int x, int l, int r) { if ((a[x] - '0') % P == 0) ++Cnt, Ans += r - l + 1; }

void delr(int x, int l, int r) { if ((a[x] - '0') % P == 0) Ans -= r - l + 1, --Cnt; }

int main () {

#ifndef ONLINE_JUDGE

    freopen("cpp.in", "r", stdin);

#endif

	scanf("%d%s%d", &P, a + 1, &Q); N = strlen(a + 1);

	for (int i = 1; i <= Q; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;

	for (int i = 1; i <= N; i++) bel[i] = (i - 1) / LEN + 1;

	sort(&q[1], &q[Q + 1]);

	pw[0] = 1; for (int i = 1; i <= N; i++) pw[i] = 10ll * pw[i - 1] % P;

	for (int i = N; i; i--) s[i] = (s[i + 1] + 1ll * (a[i] - '0') * pw[N - i] % P) % P;

	for (int i = 1; i <= N; i++) h[i] = s[i];

	sort(&h[1], &h[N + 2]); int size = unique(&h[1], &h[N + 2]) - h - 1;

	for (int i = 1; i <= N; i++) s[i] = lower_bound(&h[1], &h[size + 1], s[i]) - h - 1;

	int ql = 1, qr = 0;

	if (P != 2 && P != 5) {

		for (int i = 1; i <= Q; i++) {

			++q[i].r;

			while (ql < q[i].l) Ers(ql), ++ql;

			while (ql > q[i].l) --ql, Ins(ql);

			while (qr < q[i].r) ++qr, Ins(qr);

			while (qr > q[i].r) Ers(qr), --qr;

			ans[q[i].id] = Ans;

		}

	} else {

		for (int i = 1; i <= Q; i++) {

			while (ql > q[i].l) --ql, insl(ql);

			while (qr < q[i].r) ++qr, insr(qr, ql, qr);

			while (ql < q[i].l) dell(ql), ++ql;

			while (qr > q[i].r) delr(qr, ql, qr), --qr;

			ans[q[i].id] = Ans;

		}

	}

	for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);

    return 0;

}