【bzoj4542】【HNOI2016】【大数】【莫队】

Description

　　小 B 有一个很大的数 S，长度达到了 N 位；这个数可以看成是一个串，它可能有前导 0，例如00009312345
。小B还有一个素数P。现在，小 B 提出了 M 个询问，每个询问求 S 的一个子串中有多少子串是 P 的倍数（0 也
是P 的倍数）。例如 S为0077时，其子串 007有6个子串：0,7,00,07,007；显然0077的子串007有6个子串都是素
数7的倍数。

Input

Output

Sample Input

Sample Output

//第一个询问问的是整个串，满足条件的子串分别有：121121,2112,11,121,121。

题解：

我们可以先做一个模P意义下的后缀和S.

一段数(l,r)可以被P整除意味着s[l]和s[r+1]在模P意义下相等.

把后缀和离散一下在莫队的时候我们就可以实现O(1)转移.

因为是l和r+1进行比较,我们可以把询问里所有的r都加1;

如果p=2或p=5这样做显然是不行的,因为此时10%p==0;

然后可以发现此时一段数是否是p的倍数只和最后一位有关.

所以也是可以实现O(1)转移的.

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 100010 
using namespace std;
int bk,n,bl[N],a[N],m,c[N],num;
long long p,s[N],h[N],temp,bin[N],ans[N];
char ch[N];
struct use{int l,r,id;}q[N];
bool cmp(use a,use b){
  if (bl[a.l]==bl[b.l]) return a.r<b.r;
  else return a.l<b.l;	
}
void getbk(){
  bk=sqrt(n);
  for (int i=1;i<=n;i++) bl[i]=(i-1)/bk+1;
  sort(q+1,q+m+1,cmp);
}
int find(int x){
  int l=1,r=n;
  while (l<=r){
    int mid=(l+r)>>1;
	if (x<h[mid]) r=mid-1;
	else if (x>h[mid]) l=mid+1;
	else return mid;
  }
}
void pre(){
  bin[0]=1;
  for (int i=1;i<=n;i++) bin[i]=(bin[i-1]*10)%p;
  if (p!=2&&p!=5){
    for (int i=n;i>=1;i--) s[i]=(s[i+1]+a[i]*bin[n-i]%p)%p;	
	for (int i=1;i<=n;i++) h[i]=s[i];n++;h[n]=0;
    sort(h+1,h+n+1);
    for (int i=1;i<=n;i++) s[i]=find(s[i]);
    n--;
  }
  else{
    for (int i=1;i<=n;i++)  s[i]=a[i]%p;
  }
}
void add(int x){temp+=(long long)c[x];c[x]++;}
void del(int x){c[x]--;temp-=(long long)c[x];}
void solve(){
  int l=1,r=0; 
  for (int i=1;i<=m;i++){
    q[i].r++;   
	while (l<q[i].l){del(s[l]);l++;}
	while (l>q[i].l){l--;add(s[l]);}
	while (r<q[i].r){r++;add(s[r]);}
	while (r>q[i].r){del(s[r]);r--;}
	ans[q[i].id]=temp;
  }
}
void solve2(){
  int l=1,r=0;
  for (int i=1;i<=m;i++){
    while (l<q[i].l){temp-=c[0];c[s[l]]--;l++;}
    while (l>q[i].l){l--;c[s[l]]++;temp+=c[0];}
    while (r<q[i].r){r++;if (s[r]==0) temp+=(r-l+1);c[s[r]]++;}
	while (r>q[i].r){if (s[r]==0) temp-=(r-l+1);c[s[r]]--;r--;} 
    ans[q[i].id]=temp;
  }
}
int main(){
  scanf("%lld",&p);scanf("%s",ch);
  n=strlen(ch);scanf("%d",&m);
  for (int i=0;i<n;i++) a[i+1]=ch[i]-'0';
  for (int i=1;i<=m;i++){
    scanf("%d%d",&q[i].l,&q[i].r);
    q[i].id=i;
  }
  getbk();pre();
  if (p!=2&&p!=5) solve();
  else solve2();
  for (int i=1;i<=m;i++) printf("%lldn",ans[i]);	
}

（编辑：东莞站长网）

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