C++(clang++ 11.0.1) 解法, 执行用时: 169ms, 内存消耗: 4560K, 提交时间: 2023-03-31 19:34:57

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <climits>
#define LL long long
using namespace std;
const int MAXN = 2e5 + 5;
int p, m, t, a[MAXN], lsh[MAXN], f, l = 1, r = 0, c[MAXN], n, pre[MAXN];
char s[MAXN];
LL ans[MAXN], res;
struct Node {
	int X, Y, pos;
	bool operator < (const Node P) const { return X / t != P.X / t ? X < P.X : Y < P.Y; }
}query[MAXN];
void Add(int x, int F) {
	if(f) c[a[x]] ++, F ? res += (a[x] % p == 0) * (r - l + 1) : res += c[a[x]];
	else res += c[pre[x]], c[pre[x]] ++; 
}
void Del(int x, int F) {
	if(f) F ? res -= (a[x] % p == 0) * (r - l + 1 + 1) : res -= c[a[x]], c[a[x]] --;
	else c[pre[x]] --, res -= c[pre[x]];
}
int main() {
	int qwq = 1;
	scanf("%d%s%d", &p, s + 1, &m); n = strlen(s + 1); t = sqrt(n);
	for(int i = 1; i <= n; i ++) a[i] = s[i] - '0';
	for(int i = n; i >= 1; i --) pre[i] = (LL)(pre[i + 1] + (LL)qwq * a[i]) % p, qwq = ((LL)qwq * 10) % p, lsh[i] = pre[i];
	for(int i = 1; i <= m; i ++) scanf("%d%d", &query[i].X, &query[i].Y), query[i].Y ++, query[i].pos = i;
	sort(query + 1, query + 1 + m);
	sort(lsh + 1, lsh + 2 + n);
	int len = unique(lsh + 1, lsh + 2 + n) - lsh - 1; 
	for(int i = 1; i <= n + 1; i ++) pre[i] = lower_bound(lsh + 1, lsh + 1 + len, pre[i]) - lsh;
	if(p == 2 || p == 5) f = 1;
	for(int i = 1; i <= m; i ++) {
		if(f) query[i].Y --;
		while(l < query[i].X) Del(l ++, 0);
		while(l > query[i].X) Add(-- l, 0);
		while(r < query[i].Y) Add(++ r, 1);
		while(r > query[i].Y) Del(r --, 1);
		ans[query[i].pos] = res;
	}
	for(int i = 1; i <= m; i ++) printf("%lld\n", ans[i]);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 284ms, 内存消耗: 10208K, 提交时间: 2019-08-11 20:35:14

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000
int m,n,i,j,S=300,P,nl,nr;
long long now;
char c[maxn+10];
long long cnt[maxn+10],a[maxn+10],b[maxn+10];
map<long long ,long long>mp;
struct ask
{
	int l,r,id;
	long long ans;
}s[maxn+10];
bool cmp(ask p,ask q)
{
	if((p.l-1)/S!=(q.l-1)/S)
	return p.l<q.l;
	return p.r<q.r;
}
bool cmp2(ask p,ask q)
{
	return p.id<q.id;
}
void add(int x)
{
//	printf("!%d ",x);
	now+=cnt[a[x]]++;
}
void del(int x)
{
//	printf("?%d ",x);
	now-=--cnt[a[x]];
}
int modui(int ql,int qr)
{
	while(qr>nr)add(++nr);//ºó¼Ó 
	while(ql<nl)add(--nl);//Ç°¼Ó 
	while(qr<nr)del(nr--);//ºó¼õ 
	while(ql>nl)del(nl++);//Ç°¼õ 
	return now;
}
int main()
{
	scanf("%d\n",&P);
	scanf("%s",c);
	n=strlen(c);
	for(i=0;i<n;i++)
	{
		a[i+1]=c[i]-'0';
		
	}
	
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&s[i].l,&s[i].r);
		s[i].id=i;
	}
	if(P==2||P==5)
	{
		long long sum=0;
		for(i=1;i<=n;i++)
		{
			if(a[i]%P==0)
			{
				a[i]=a[i-1]+i;
				b[i]=b[i-1]+1;
			}
			else
			{
				a[i]=a[i-1];
				b[i]=b[i-1];
			}
		}
		for(i=1;i<=m;i++)
		{
			printf("%lld\n",a[s[i].r]-a[s[i].l-1]-(b[s[i].r]-b[s[i].l-1])*(s[i].l-1));
		}
		return 0;
	}
	long long k=1;
	for(i=n;i>=1;i--)
	{
		a[i]=(a[i]*k+a[i+1])%P;
		b[i]=a[i];
		k=k*10%P;
	}
	sort(b+1,b+1+n);
	for(i=1;i<=n+1;i++)
	mp[b[i]]=i;
	for(i=1;i<=n+1;i++)
	a[i]=mp[a[i]];
	sort(s+1,s+1+m,cmp);
	nl=1,nr=0,now=0;
	for(i=1;i<=m;i++)
	{
		s[i].ans=modui(s[i].l,s[i].r+1);
	}
	sort(s+1,s+1+m,cmp2);
	for(i=1;i<=m;i++)
	{
		printf("%lld\n",s[i].ans);
	}
	return 0;
}