正经题解在最下面
写的时候看了大神的题解[就是上面那个网址],看到下面这段话
观察题目，发现一串数s(l~r)整除p满足s(l~n-1)%p==s(r+1~n-1)%p
但p值为2或5不满足这个性质需要特判（不过数据中好像没有，于是笔者没写，有兴趣的可以自己去写写。。。。。。）
然后问题转化为求一段区间中有几对相等的f值。
看到这里,我感觉豁然开朗,完全忽视了离散化的要求,我以为把余数值存起来扫一遍就行了离散个p啊..
写着写着完全参透这道题之后发现离散化的是余数啊,你不离散化怎么存数量啊,不存某个余数数量硬扫肯定超时啊....
然后我暴力硬扫果然[dian]超时了.........
然后老老实实写离散化..........
最重要的:2和5要特判
更重要的:离散化的时候要注意判定0的情况...即等于0时特判,不等0时离散化的赋值不应该从0开始,看加注释的那一段即可,不然会像我一样不停错两个点.....
我的程序200+大牛程序100-行..被吊着打.......我觉得我写的还挺清晰的...虽然完全不简洁
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int p,m,s=,sz;
int a[]={};
int bel[]={};
int ans[]={};
long long mo[]={};
long long b[]={};
long long re[][]={};
int vis[]={};
int tot[]={};
struct nod{
int x,y;
int id;
}e[];
void readin(){
char c=getchar();
while(c<''||c>''){
c=getchar();
}
while(c>=''&&c<=''){
a[++s]=(int)(c-'');
c=getchar();
}
}
bool mmp(nod aa,nod bb){
if(bel[aa.x]==bel[bb.x]){
if(aa.y==bb.y){
return aa.x<bb.x;
}
return aa.y<bb.y;
}
return bel[aa.x]<bel[bb.x];
}
void work(){
int l=,r=;
int an=;
for(int i=;i<=m;i++){
while(l>e[i].x){
l--;
an+=vis[mo[l]];
if(mo[r+]==mo[l]){
an+=;
}
vis[mo[l]]++;
}
while(r<e[i].y){
r++;
vis[mo[r]]++;
an+=vis[mo[r+]];
}
while(l<e[i].x){
vis[mo[l]]--;
an-=vis[mo[l]];
if(mo[r+]==mo[l]){
an-=;
}
l++;
}
while(r>e[i].y){
an-=vis[mo[r+]];
vis[mo[r]]--;
r--;
}
ans[e[i].id]=an;
}
for(int i=;i<=m;i++){
printf("%d\n",ans[i]);
}
}
void work5(){
int l=,r=;
int an=;
for(int i=;i<=m;i++){
while(l>e[i].x){
l--;
vis[a[l]%p]++;
an+=vis[];
}
while(r<e[i].y){
r++;
vis[a[r]%p]++;
if(a[r]%p==){
an+=r-l+;
}
}
while(l<e[i].x){
an-=vis[];
vis[a[l%p]]--;
l++;
}
while(r>e[i].y){
if(a[r]%p==){
an-=r-l+;
}
vis[a[r]%p]--;
r--;
}
ans[e[i].id]=an;
}
for(int i=;i<=m;i++){
printf("%d\n",ans[i]);
}
}
int main(){
//freopen("wtf.in","r",stdin);
scanf("%d",&p);
readin();
sz=(int)sqrt((double)s);
scanf("%d",&m);
for(int i=;i<=m;i++){
scanf("%d%d",&e[i].x,&e[i].y);
if(e[i].x>=s){
e[i].x=s;
}
if(e[i].y>s){
e[i].y=s;
}
e[i].id=i;
}
for(int i=;i<=s;i++){
bel[i]=(i-)/sz+;
}
sort(e+,e++m,mmp);
if(p==||p==){
work5();
return ;
}
for(int i=;i<=;i++){
re[i][]=i%p;
tot[i]=;
}
for(int i=s,w=;i>=;i--){
int x=a[i];
while(tot[x]<w){
tot[x]++;
re[x][tot[x]]=re[x][tot[x]-]*%p;
}
mo[i]=(re[x][w]+mo[i+])%p;
b[i]=mo[i];
w++;
}
sort(b+,b++s);
int size=unique(b+,b++s)-b-;
for(int i=;i<=s;i++){//离散化部分....注意一定要特判..
if(mo[i]==){
mo[i]==;
}
else{
mo[i]=lower_bound(b+,b++s,mo[i])-b;//这里-1且输入字符串中没有0时,1会被离散化为0
}
}
work();
return ;
}