BZOJ4542: [Hnoi2016]大数【逆元+莫队】

4542: [Hnoi2016]大数

【题目描述】

传送门

【题解】

造前缀和Sum[i]=Sum[i-1] * 10+Num ,先不考虑MOD,L到R之间的数就是Sum[R]-Sum[L-1] * 10^{R-L+1} ,这个数得等于0,于是得到这样的方程:

Sum[R]-Sum[L-1] * 10^{R-L+1}=0(Mod P)

移向得Sum[R]=Sum[L-1] * 10^{R-L+1}(Mod P)

整理后得Sum[R] * 10^{-R}=Sum[L-1] * 10^{-(L-1)}(Mod P)

f(x)=Sum[x] * 10^{-R} ,可以用逆元。

这题就变成了在L到R之间有多少对[l,r]使f(l)==f(r)

显然可以离线处理,所以果断莫队。

代码如下

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
typedef long long LL;
LL P,n,m,blo,Now,Sum[MAXN],Ans[MAXN],B[MAXN],hsh[MAXN];char s[MAXN];
struct xcw{
    int L,R,id;
    bool operator <(const xcw b)const{return (L/blo<b.L/blo)||(L/blo==b.L/blo&&R<b.R);}
}a[MAXN];
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
LL ksm(LL w,int x){
    LL Ans=1;
    for(;x;x>>=1,w=(w*w)%P) if(x&1) Ans=Ans*w%P;
    return Ans;
}
void Add(int x){Now+=hsh[x],hsh[x]++;}
void Del(int x){--hsh[x],Now-=hsh[x];}
int main(){
    scanf("%d%s%d",&P,s+1,&m);n=strlen(s+1);
    if(P==2||P==5){
        for(int i=1;i<=n;i++) if(Ans[i]=Ans[i-1],B[i]=B[i-1],(s[i]-48)%P==0) Ans[i]+=i,B[i]++;
        int L,R;while(m--) L=read()-1,R=read(),printf("%lld\n",Ans[R]-Ans[L]-(B[R]-B[L])*L);
        return 0;
    }
    for(int i=1;i<=n;i++) Sum[i]=(Sum[i-1]*10+s[i]-48)%P;
    LL V=1;blo=sqrt(n);
    for(int i=0;i<=n;i++) B[i]=Sum[i]=Sum[i]*ksm(V,P-2)%P,V=V*10%P;
    sort(B,B+1+n);int len=unique(B,B+1+n)-B-1;
    for(int i=0;i<=n;i++) Sum[i]=lower_bound(B,B+1+len,Sum[i])-B;
    for(int i=1;i<=m;i++) a[i]=(xcw){read()-1,read(),i};
    sort(a+1,a+1+m);
    int L=0,R=-1;
    for(int i=1;i<=m;i++){
        while(L<a[i].L) Del(Sum[L++]);
        while(L>a[i].L) Add(Sum[--L]);
        while(R<a[i].R) Add(Sum[++R]);
        while(R>a[i].R) Del(Sum[R--]);
        Ans[a[i].id]=Now;
    }
    for(int i=1;i<=m;i++) printf("%lld\n",Ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部