【LG P3245】 [HNOI2016]大数

Cxs3 · 2020-07-31 14:21:08 · 题解

题目链接:https://www.luogu.com.cn/problem/P3245

\text{Solution}

为方便起见，我们用[L,R]表示S[L...R]这段数字，用sum[i]表示S[i...n]的值。
则易得：

[L,R]\times10^{n-R}=sum[L]-sum[R+1]

\Rightarrow [L,R]=\frac{sum[L]-sum[R+1]}{10^{n-R}}

当10^{n-R}与P互质时（即P\neq2且P\neq5）：
若[L,R]\ mod\ P=0，则： \frac{sum[L]-sum[R+1]}{10^{n-R}}\ mod\ P=0 \Rightarrow(sum[L]-sum[R+1])\ mod\ P=0 \Rightarrow sum[L]\ mod\ P =sum[R+1]\ mod\ P
这时我们让sum[i]的意义改变：表示S[i...n]的值mod\ P后的余数。
也就是说，若sum[L]=sum[R+1]，则[L,R]\ mod\ P=0.
这样问题就转化为求sum[L...R+1]中相等的数字有多少对。
由此，这道题就变成了小Z的袜子，可以用莫队来求解。

我们用cnt[sum[x]]表示在当前区间[L,R]中值为sum[x]的点有多少个。每当加进来一个点x时，这个点可以分别与[L,R]中cnt[sum[x]]个点配对成一对（因为值相同，都是sum[x]），则当前答案nowans+=cnt[sum[x]].删去点x时也同理。
需要注意的是，由于sum[x]太大，需要进行离散化才能作为数组下标。
还有就是，若sum[x]=0，则这个点不用与其他点配对，自己本身就可以作为一种答案，所以在代码中新加一个值为0的点（sum[n+1]=0），与之配对来计入这一部分答案。

当10^{n-R}与P不互质时（即P=2或P=5）：
这时问题就更简单了，因为是10进制，若最后一位能被P整除，则这个数字就可以被P整除。即若a[i]\ mod\ P=0，答案就增加i个。
对于每一个询问，计算每一位的贡献做前缀和即可。

\text{Code}

#include<bits/stdc++.h>
#define ll long long
const int N=2e5+10;
using namespace std;

struct node
{
    ll l,r,id;
}h[N];
struct date
{
    ll d,id;
}s[N];
ll n,m,size,p;
ll a[N],num[N],bl[N],cnt[N],now,ans[N];
char c[N];

ll read()
{
    ll a,f=1;
    char c;
    c=getchar();
    while(!isdigit(c)){f=c=='-'?-1:f; c=getchar();}
    a=c-'0'; c=getchar();
    while(isdigit(c)){a=a*10+c-'0'; c=getchar();}
    return a*f;
}

void solve()
{
    ll i,l,r,tot,mus;
    for(i=1;i<=n;i++)
    {
      s[i]=s[i-1];
      if(a[i]%p==0){s[i].d+=i; s[i].id++;}
    }
    m=read();
    while(m--)
    {
      l=read(); r=read();
      tot=s[r].d-s[l-1].d;//全部的贡献 
      mus=(l-1)*(s[r].id-s[l-1].id);//区间[1,l-1]里产生的贡献 
      printf("%lld\n",tot-mus);//相减得到[l,r]里的贡献 
    }
}

bool cmp1(date x,date y){return x.d<y.d;}

void prework()
{
    ll i,len=0,pow=1;
    size=sqrt(n);//莫队分块的时候，不能在n++之后分，不然会出问题emmm 
    bl[n+1]=n/size+1;
    for(i=n;i>0;i--)//算出[i,n]这段数字%p的余数 
    {
      s[i].d=(s[i+1].d+a[i]*pow)%p;
      s[i].id=i; pow=pow*10%p;//s[i].id用来记录原来的编号 
      bl[i]=(i-1)/size+1;//顺便分块 
    }
    s[++n].d=0; s[n].id=n;//新加一个点 
    sort(s+1,s+n+1,cmp1);
    for(i=1;i<=n;i++)//（非常朴素的）离散化 
    {
      if(i==1||s[i].d!=s[i-1].d) len++;
      num[s[i].id]=len;
    }
}

bool cmp2(node x,node y)
{
    if(bl[x.l]^bl[y.l]) return bl[x.l]<bl[y.l];
    return (bl[x.l]&1)?(x.r<y.r):(x.r>y.r);
    //莫队排序小技巧： 奇数块升序，偶数块降序 
}

void add(ll x){now+=cnt[num[x]]; cnt[num[x]]++;}
//注意now与cnt数组改变的先后顺序 
void del(ll x){cnt[num[x]]--; now-=cnt[num[x]];}

int main()
{
    ll i,j,l,r;
    p=read(); scanf("%s",c);
    n=strlen(c);
    for(i=1;i<=n;i++) a[i]=c[i-1]-'0';
    if(p==2||p==5){solve(); return 0;}//特判 
    prework();
    m=read();
    for(i=1;i<=m;i++)
    {
      h[i].l=read();
      h[i].r=read()+1;//在这里就+1 
      h[i].id=i;
    }
    sort(h+1,h+m+1,cmp2);
    l=1; r=0;
    for(i=1;i<=m;i++)//莫队 
    {
      while(l<h[i].l) del(l++);
      while(l>h[i].l) add(--l);
      while(r<h[i].r) add(++r);
      while(r>h[i].r) del(r--);
      ans[h[i].id]=now;
    }
    for(i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}