自动搬运

查看原文

来自洛谷，原作者为

	Cxs3 这个家伙很懒，什么也不想留下

搬运于2025-08-24 21:46:54，当前版本为作者最后更新于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;
}