【BZOJ 4542】大数 【莫队】
发布时间:2020-12-14 01:28:45 所属栏目:大数据 来源:网络整理
导读:思路:当P!=2或5时,显然10^x%P!=0 把后缀模P的值搞出来 于是问题就便成询问区间内%P为x的分别有多少个 这个再套一个莫队就可以了。 我的代码压行比较丑,我放std的代码。 #includecmath #includecstdio #includecstring #includeiostream #includealgorith
思路:当P!=2或5时,显然10^x%P!=0 把后缀模P的值搞出来 于是问题就便成询问区间内%P为x的分别有多少个 这个再套一个莫队就可以了。 #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;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |