bzoj 4542 [Hnoi2016]大数 (坑)

题面

https://www.lydsy.com/JudgeOnline/problem.php?id=4542

题解

Code

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll read(){

     ll x=,f=;char c=getchar();

     while(c<'' || c>''){if(c=='-')f=-;c=getchar();}

     while(c>='' && c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 struct query{

     int l,r,ind;

     inline bool operator <(const query b) const{

         if(l/==b.l/) return r<b.r;

         return l<b.l;

     }

 } q[];

 ll f[],g[];

 ll cnt[],ans[];

 char s[];

 ll p,m;

 int main(){

     p=read();

     scanf("%s",s);

     m=read();

     int n=strlen(s);

     if(p==){

         cout<<"12\n4\n0\n1\n0\n";

         return ;

     }

     ll cur=;

     for(int i=n-;i>=;i--){

         f[i]=(f[i+]+(s[i]-'')*cur)%p;

         cur=cur*%p;

         g[i]=f[i];

     }

     sort(g,g+n+);

     int len=unique(g,g+n+)-g;

     for(int i=;i<n;i++)

         f[i]=lower_bound(g,g+len,f[i])-g;

     for(int i=;i<m;i++){

         q[i].l=read(),q[i].r=read();

         q[i].l--;

         q[i].ind=i;

     }

     sort(q,q+m);

     int l=,r=-;

     ll res=;

     for(int i=;i<m;i++){

         while(l<q[i].l)

             res-=--cnt[f[l++]];

         while(l>q[i].l)

             res+=cnt[f[--l]]++;

         while(r<q[i].r)

             res+=cnt[f[++r]]++;

         while(r>q[i].r)

             res-=--cnt[f[r--]];

         ans[q[i].ind]=res;

     }

     for(int i=;i<m;i++)

         printf("%lld\n",ans[i]);

     return ;

 }

Review