[HNOI2016]大数

第一次做这种莫队，但是乱调一会儿参数就过去了。

传送门

可以看出是莫队，但怎么做呢？

首先要能把$[l,r]​$这个串形成的数在$\% p​$下表示出来，存一下后缀，$rs[i]​$表示i到n形成的数$\%p​$的值。

那么$[l,r]​$的数$num(l,r)≡\frac{rs[l]-rs[r+1]}{10^{r-l+1}}(mod\ p)​$

当$10^{r-l+1}\%p\ne0$时：$num(l,r)\times10^{r-l+1}≡rs[l]-rsr+1$

所以如果$rs[l]=rs[r+1]$，$num(l,r)$就是p的倍数，条件是$gcd(10,p)=1$，p不能是2或5。

p=2或5的情况很好判断，可以写一个前缀和，但我又写了一个莫队。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
struct node{
    int l,r,h;
}q[200001];
struct number{
    ll z,h;
}b[200021];
int bl[200001],ro[200021],n,m,p,l,r,blo;
int a[200021],sum,cnt;
ll rs[200021],ans[200001],w[200021];
inline bool cmp1(node c,node d){
    if (bl[c.l]!=bl[d.l]) return c.l<d.l;
    if (bl[c.l]%2) return c.r<d.r;
    return c.r>d.r;
}
inline bool cmp2(number c,number d){
    return c.z<d.z;
}
inline void addl(int x){cnt+=(a[x]%p==0);sum+=cnt;}
inline void addr(int x){sum+=(r-l+1)*(a[x]%p==0);cnt+=(a[x]%p==0);}
inline void dell(int x){sum-=cnt;cnt-=(a[x]%p==0);}
inline void delr(int x){sum-=(r-l+1)*(a[x]%p==0);cnt-=(a[x]%p==0);}
inline void add(int x){sum+=ro[rs[x]]; ro[rs[x]]++;}
inline void del(int x){ro[rs[x]]--; sum-=ro[rs[x]];}
int main(){
    char ch[200021];
//	string c;	c.size()
    scanf("%d",&p); scanf("%s",ch+1);
    n=strlen(ch+1); blo=sqrt(n);
    for (int i=1; i<=n; i++){
        a[i]=ch[i]-'0';
        bl[i]=(i-1)/blo+1;
    }
    w[1]=1;
    for (int i=2; i<=n; i++) w[i]=w[i-1]*10%p;
    if (p!=2&&p!=5){
        for (int i=n; i>=1; i--){
            b[i].z=(b[i+1].z+a[i]*w[n-i+1])%p;
            b[i].h=i;
        }
        b[n+1].h=n+1; b[n+1].z=0;
        sort(b+1,b+n+2,cmp2);
        for (int i=1; i<=n+1; i++)
            rs[b[i].h]=rs[b[i-1].h]+(b[i].z!=b[i-1].z);
    }
//	printf("%d\n",n);
//	for (int i=1; i<=n; i++) printf("%d ",ls[i]);
    scanf("%d",&m);
    for (int i=1; i<=m; i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].h=i;
    }
    sort(q+1,q+m+1,cmp1);
//	ro[0]=1; 
    l=1;// sum=(a[1]%p==0); lo[ls[1]]=1; ro[rs[1]]=1;
    if (p!=2&&p!=5){
        for (int i=1; i<=m; i++){
            while (l<q[i].l) del(l),l++;
            while (l>q[i].l) l--,add(l);
            while (r>q[i].r+1) del(r),r--;
            while (r<q[i].r+1) r++,add(r);
            ans[q[i].h]=sum;			
        }
    }
    else{
//		sum=cnt=(a[1]%p==0);
        for (int i=1; i<=m; i++){
            while (l<q[i].l) dell(l),l++;
            while (l>q[i].l) l--,addl(l);
            while (r>q[i].r) delr(r),r--;
            while (r<q[i].r) r++,addr(r);
            ans[q[i].h]=sum;
        }		
    }
    for (int i=1; i<=m; i++) printf("%d\n",ans[i]);
    return 0;
}