HNOI2016 大数(number)

分析

首先，我们要知道取模的几个性质：
设p=a+b，q=a*b
1.p%x=(a%x+b%x)%x
2.q%x=(a%x*b%x)%x
知道这两个性质之后，我们首先输入进要模的数x和字符串s，处理出一个后缀数组m，和一个po数组，m[i]表示字符串中从前往后数的第i位到结尾所组成的数字对x取模的结果是多少，po[i]表示10^i对x取模的结果。以样例来说明，m[3]表示1211对11取模的结果，则m[3]=1。
然后我们根据上面两条性质，可以知道，要让[i,j]这一个区间组成的数字能被x整除，就要使m[i]=m[j]。为什么呢？用一个图来说明，如图所示。

可以知道，设m[i]组成的数是p'，m[j]组成的数是a'，k组成的数是b'，则可知b'*10^(n-j)+a'=p'，那么m[i]=(k*po[n-j])%x+m[j]，因为要让k=0所以就要满足m[i]==m[j]。但是在这里需要注意一下，由于当x=2,5的时候m[i]==m[j]是（基本上）始终满足的，因为10^o除了o=0以外都可以整除2,5所以要特判一下。不过由于数据中没有模数为2,5的情况，所以偷懒没写- -。
于是做好这个之后，离散化一下，求解就很简单了。我们可以定义一个l和r，给它们附一个初值，然后慢慢地挪到询问的位置，用桶来存每个m出现的次数，很容易可以得到答案。
但是这样还不够快。就要用到莫队的思想了。
我们将每一个l,r看做二维平面上的点，那么要让“挪过去”的复杂度最小，也就是连接每个点的曼哈顿距离总和最小。简单不严谨的写法就是，将这些点按横坐标排序，分块，然后每个块中按纵坐标排序，然后进行答案的计算。
其余的细节就给大家思考了。

代码如下

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=200003;
struct query{
    int l,r,id;
    ll ans=0;
}q[maxn];

bool cmp1(query a,query b){
    return a.l<=b.l?1:0;
}

bool cmp2(query a,query b){
    return a.r<=b.r?1:0;
}

bool cmp3(query a,query b){
    return a.r>=b.r?1:0;
}

bool cmp4(query a,query b){
    return a.id<b.id?1:0;
}

char a[maxn];
ll c[maxn],m[maxn],po[maxn],mo;
int buk[maxn],n,lim,k;
int main(){
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    scanf("%lld",&mo);
    scanf("%s",&a);

    scanf("%d",&lim);
    k=sqrt(lim);
    for(int i=1;i<=lim;i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+lim+1,cmp1);

    bool flag=0;
    for(int i=1;i<=lim;i+=k,flag^=1)
        if(flag)sort(q+i,q+min(k+i,lim+1),cmp3);
        else sort(q+i,cmp2);

    n=strlen(a);
    m[n]=0;po[0]=1%mo;
    for(int i=n;i>0;i--){
        po[n-i+1]=(po[n-i]*(10%mo))%mo;
        m[i]=(m[i+1]+(((a[i-1]-'0')%mo)*(po[n-i]%mo)))%mo;
        c[i]=m[i];
    }
    sort(c+1,c+n+2);
    int left=1,right=2;c[1]=m[1];
    while(right<=n+1){
        while(right<=n+1&&c[right]==c[left])right++;
        if(right<=n+1)c[++left]=c[right];
    }
    int l,mid;
    for(int i=1;i<=n+1;i++){
        l=1,r=left+1;
        while(l+1<r){
            mid=(l+r)/2;
            if(c[mid]<=m[i])l=mid;
            else r=mid;
        }
        m[i]=l;
    }
    ll ql,qr,ans=0;
    l=1,r=2;
    for(int i=1;i<=lim;i++){
        ql=q[i].l,qr=q[i].r;
        while(l<ql)
            l++,buk[m[l]]--,ans-=buk[m[l]];
        while(l>=ql)
            ans+=buk[m[l]],buk[m[l]]++,l--;
        while(r>qr)
            r--,buk[m[r]]--,ans-=buk[m[r]];
        while(r<=qr+1)
            ans+=buk[m[r]],buk[m[r]]++,r++;
        q[i].ans=ans;
    }
    sort(q+1,cmp4);
    for(int i=1;i<=lim;i++)printf("%lld\n",q[i].ans);
    return 0;
}