4542: [Hnoi2016]大数 莫队算法

555我好弱啊
都说今年的HNOI是无脑数据结构赛，都很好想只是码代码的问题，然而我还是不会做这道题。
要退役了啊啊啊。

首先我们令 si 表示以 i 为开头的后缀形成的数字。
对于 p≠2 且 p≠5 的时候，我们可以发现，若存在 l,r ，满足 sl≡sr+1(modp) ，则区间 [l,r] 组成的数字一定是 p 的倍数，那么问题转化为求区间中有多少相同的数的对数，就可以用莫队算法来解决了。
当 p=2 或 p=5 的时候，预处理一下就好了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

const int N=100005;
int n,m,cnt,block;
long long p,ans;
char str[N];
int belong[N],id[N],num[N];
long long s1[N],s2[N];
long long s[N],Ans[N];
map<long long,int> mp;
struct query
{
    int l,r,id;
}q[N];

inline long long read()
{
    long long a=0,f=1; char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
    while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
    return a*f;
}

inline bool operator<(query a,query b)
{
    return belong[a.l]==belong[b.l]?a.r<b.r:a.l<b.l;
}

long long get(long long x)
{
    return x*(x-1)>>1ll;
}

inline void solve()
{
    for (int i=1;i<=n;i++)
        if (str[i]%p==0)
            s1[i]=s1[i-1]+1,s2[i]=s2[i-1]+i;
        else s1[i]=s1[i-1],s2[i]=s2[i-1];
    m=read();
    for (int i=1;i<=m;i++)
    {
        int l=read(),r=read();
        printf("%lldn",s2[r]-s2[l-1]-(s1[r]-s1[l-1])*(l-1));
    }
}

int main()
{
    p=read();
    scanf("%s",str+1);
    n=strlen(str+1);
    for (int i=1;i<=n;i++) str[i]-='0';
    if (p==2||p==5) {solve(); return 0;}
    block=(int)sqrt(n);
    for (int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    long long base=1;
    for (int i=n;i;i--)
    {       
        base=base*10%p;
        s[i]=(s[i+1]+str[i]*base%p)%p;  
        if (!mp[s[i]]) mp[s[i]]=++cnt;
    }
    for (int i=1;i<=n+1;i++) id[i]=mp[s[i]];
    m=read();
    for (int i=1;i<=m;i++)
        q[i].l=read(),q[i].r=read()+1,q[i].id=i;
    sort(q+1,q+m+1);
    int l=1,r=0;
    for (int i=1;i<=m;i++)
    {
        for (;r>q[i].r;r--) ans-=get(num[id[r]]),num[id[r]]--,ans+=get(num[id[r]]);
        for (;r<q[i].r;r++) ans-=get(num[id[r+1]]),num[id[r+1]]++,ans+=get(num[id[r+1]]);
        for (;l<q[i].l;l++) ans-=get(num[id[l]]),num[id[l]]--,ans+=get(num[id[l]]);
        for (;l>q[i].l;l--) ans-=get(num[id[l-1]]),num[id[l-1]]++,ans+=get(num[id[l-1]]);
        Ans[q[i].id]=ans;
    }
    for (int i=1;i<=m;i++)
        printf("%lldn",Ans[i]);
    return 0;
}

（编辑：核心网）

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