首先$P=2 or 5$ 是容易的 我们先不考虑这两种情况 这样可以使得$(10,P)=1$ 也就是说 此时我们把每个$a_i$乘上$10^{n-i}$ 就能够将取区间所对应的十进制数转化为区间求和

首先考虑单测的情况 那就是对整个序列扫一遍 若两个位置前缀和相同则计入一次答案

然后我们发现 这个东西等价于 求解序列内相同点对个数

套一个莫队 用$cnt$记录当前前缀和的出现次数 然后没了

注意要提前对前缀和离散化 不然会炸 复杂度$O(n\sqrt n)$

原题:P3245

我已疾苦 今天全天在这个题上用了4h 感觉状态好差

#include<bits/stdc++.h>
#define int long long 
#define big __int128
#define pii pair<int,int>
#define F first
#define S second
#define mkp make_pair 
using namespace std;
const int inf=1e9,mod=998244353;
const int N=2e5*1.01,B=450;
int P,n,a[N];
string s;
int f10[N],T,qtt,kn;
int K(int x){return (x)/B+1;}
struct Query{
	int l,r,id;
}qry[N];
bool cmp(Query x,Query y){
	if(K(x.l)==K(y.l)){
		if(K(x.l)&1) return x.r<y.r;
		return x.r>y.r;
	}return x.l<y.l;
}
int cnt[N],b[N],nans;
unordered_map<int,int>mp; 
void add(int x){
	nans+=cnt[a[x]];
	cnt[a[x]]++;
}
void del(int x){
	cnt[a[x]]--;
	nans-=cnt[a[x]];
}
int scnt[N],ssum[N];
int ans[N];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("ex.in","r",stdin);
//	freopen("my.out","w",stdout);
//	system("fc ex.out my.out");return 0;
	cin>>P>>s;f10[0]=1;
	for(int i=1;i<=200000;i++) f10[i]=f10[i-1]*10%P;
	n=s.size();kn=K(n);
	if(P==2||P==5){
		for(int i=1;i<=n;i++){
			a[i]=s[i-1]-'0';
			if(a[i]%P==0){scnt[i]=1;ssum[i]=i;}
		}for(int i=1;i<=n;i++){
			scnt[i]+=scnt[i-1];ssum[i]+=ssum[i-1];
		}
		cin>>T;
		while(T--){
			int L,R;
			cin>>L>>R;
			cout<<ssum[R]-ssum[L-1]-(L-1)*(scnt[R]-scnt[L-1])<<"\n";
		}return 0;
	}
	
	for(int i=1;i<=n;i++){
		a[i]=s[i-1]-'0';
		a[i]=a[i]*f10[n-i]%P;
		a[i]=(a[i]+a[i-1])%P;
		b[i]=a[i];
	}b[n+1]=0;
	sort(b+1,b+n+2);
	int btt=unique(b+1,b+n+2)-b-1;
	for(int i=1;i<=btt;i++) mp[b[i]]=i;
	for(int i=1;i<=n;i++) a[i]=mp[a[i]];
	a[0]=mp[a[0]];
	cin>>T;
	for(int i=1;i<=T;i++){
		int L,R;
		cin>>L>>R;L--;
		qry[i]={L,R,i}; 
	}sort(qry+1,qry+T+1,cmp);
	int nl=1,nr=0;
	for(int i=1;i<=T;i++){
		int ql=qry[i].l,qr=qry[i].r,qid=qry[i].id;
		while(nr<qr) add(++nr);
		while(nl>ql) add(--nl);
		while(nr>qr) del(nr--);
		while(nl<ql) del(nl++);
		ans[qid]=nans;		
	}for(int i=1;i<=T;i++) cout<<ans[i]<<"\n";
	return 0;
}