【BZOJ 4542】大数 【莫队】

思路：当P！=2或5时，显然10^x%P!=0

把后缀模P的值搞出来

于是问题就便成询问区间内%P为x的分别有多少个

这个再套一个莫队就可以了。
我的代码压行比较丑，我放std的代码。

#include<cmath> 
#include<cstdio> 
#include<cstring> 
#include<iostream> 
#include<algorithm> 
const int maxn=100010;  
typedef long long ll;  
using namespace std;  
struct quer{int l,r,id;}q[maxn];  
ll ans[maxn],mod,a[maxn],n,m,pw[maxn],b[maxn],c[maxn],bel[maxn],tot,sz,cnt[maxn],now=0,scnt[maxn],ssum[maxn];char s[maxn];  
bool cmp(quer a,quer b){return bel[a.l]!=bel[b.l]?bel[a.l]<bel[b.l]:a.r<b.r;}  
bool back(quer a,quer b){return a.id<b.id;}  

void init(){  
    scanf("%lld%s%lld",&mod,s+1,&m),n=strlen(s+1),sz=(int)sqrt(n);  
    pw[0]=1;for (int i=1;i<=n;i++) pw[i]=pw[i-1]*10%mod;  
    for (int i=1;i<=n;i++) a[i]=s[i]-'0',bel[i]=(i-1)/sz+1;  
    for (int i=n;i;i--) b[i]=(b[i+1]+a[i]*pw[n-i])%mod;//后缀和的模  
    b[n+1]=0;  
    memcpy(c,b,sizeof(c)),sort(c+1,c+2+n);  
    tot=unique(c+1,c+2+n)-c-1;  
    for (int i=1;i<=n+1;i++) b[i]=lower_bound(c+1,c+2+tot,b[i])-c;  
    for (int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i,q[i].r++;  

}  

inline void modify(int p,int op){  
    now-=cnt[b[p]]*(cnt[b[p]]-1)/2;  
    cnt[b[p]]+=op;  
    now+=cnt[b[p]]*(cnt[b[p]]-1)/2;  
}  

void work(){  
    sort(q+1,q+1+m,cmp);  
    for (int i=1,l=1,r=0;i<=m;i++){  
        for (;r<q[i].r;r++) modify(r+1,1);  
        for (;r>q[i].r;r--) modify(r,-1);  
        for (;l<q[i].l;l++) modify(l,-1);  
        for (;l>q[i].l;l--) modify(l-1,1);  
        ans[q[i].id]=now;  
    }  
    for (int i=1;i<=m;i++) printf("%lldn",ans[i]);  
}  

void spw(){  
    for (int i=1;i<=n;i++) scnt[i]=scnt[i-1]+(a[i]%mod==0),ssum[i]=ssum[i-1]+(a[i]%mod==0?i:0);  
    for (int i=1;i<=m;i++){  
        int x=q[i].l,y=q[i].r-1;  
        printf("%lldn",ssum[y]-ssum[x-1]-1ll*(x-1)*(scnt[y]-scnt[x-1]));  
    }  
}  

int main(){  
    init();  
    if (mod==2||mod==5) spw();else work();  
    return 0;  
}

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!