bzoj4542 大数

Description

　　小 B 有一个很大的数 S，长度达到了 N 位；这个数可以看成是一个串，它可能有前导 0，例如00009312345
。小B还有一个素数P。现在，小 B 提出了 M 个询问，每个询问求 S 的一个子串中有多少子串是 P 的倍数（0 也
是P 的倍数）。例如 S为0077时，其子串 007有6个子串：0,0,7,00,07,007；显然0077的子串007有6个子串都是素
数7的倍数。

Input

　　第一行一个整数：P。第二行一个串：S。第三行一个整数：M。接下来M行，每行两个整数 fr,to，表示对S 的
子串S[fr…to]的一次询问。注意：S的最左端的数字的位置序号为 1；例如S为213567，则S[1]为 2，S[1…3]为 2
13。N,M<=100000，P为素数

Output

　　输出M行，每行一个整数，第 i行是第 i个询问的答案。

可以考虑用莫队解决区间询问

对于p!=2且p!=5，预处理串的每个后缀mod p的值，若两后缀mod p相等则它们间的一段mod p=0

若p=2或5，则一个串mod p为0当且仅当末尾能被p整除

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

typedef long long lint;

lint Ans=;

int m;

char s[];

struct Q{

    int l,r,id;

}q[];

lint ans[];

int b,l,p;

int mp[],id[];

inline bool operator<(const Q&a,const Q&b){

    if(id[a.l]!=id[b.l])return id[a.l]<id[b.l];

    return (a.r<b.r)!=(id[a.l]&);

}

namespace map{

    const int P=;

    lint xs[P];

    int ys[P],now=;

    bool d[P];

    int get(lint x){

        int w=x%P;

        while(d[w]){

            if(xs[w]==x)return ys[w];

            w+=;

            if(w>=P)w-=P;

        }

        d[w]=;xs[w]=x;

        return ys[w]=now++;

    }

}

int yv[];

inline void inc(int x){

    Ans+=yv[x]++;

}

inline void dec(int x){

    Ans-=--yv[x];

}

int main(){

    scanf("%d%s%d",&p,s+,&m);

    l=strlen(s+);

    b=double(l+)/(sqrt(m+)+)+;

    for(int i=;i<=l;i++)id[i]=(i-)/b;

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

        scanf("%d%d",&q[i].l,&q[i].r);

        q[i].id=i;

    }

    std::sort(q,q+m);

    int p10=;

    if(p!=&&p!=){

        for(int i=l;i;i--){

            mp[i]=(mp[i+]+(s[i]-48ll)*p10)%p;

            p10=p10*10ll%p;

        }

        for(int i=;i<=l+;i++)mp[i]=map::get(mp[i]);

    }else for(int i=;i<=l;i++)mp[i]=(s[i]-)%p;

    int L=,R=;

    if(p!=&&p!=)

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

        int l=q[i].l,r=q[i].r+;

        while(L<l)dec(mp[L++]);

        while(L>l)inc(mp[--L]);

        while(R<r)inc(mp[++R]);

        while(R>r)dec(mp[R--]);

        ans[q[i].id]=Ans;

    }else for(int i=,c=;i<m;i++){

        int l=q[i].l,r=q[i].r;

        while(L<l){

            Ans-=c;

            if(!mp[L++])--c;

        }

        while(L>l){

            if(!mp[--L])++c;

            Ans+=c;

        }

        while(R<r){

            if(!mp[++R])++c,Ans+=R-L+;

        }

        while(R>r){

            if(!mp[R--])Ans-=R-L+,--c;

        }

        ans[q[i].id]=Ans;

    }

    for(int i=;i<m;i++)printf("%lld\n",ans[i]);

    return ;

}

巴特西

bzoj4542 大数

Description

Input

Output

最新文章

热门文章