HNOI 2016 大数（莫队）

发表于 |
字数统计: 989字 | 阅读时长 ≈ 5min

[Hnoi2016 day2]大数

问题描述

小 B 有一个很大的数 S，长度达到了 N 位；这个数可以看成是一个串，它可能有前导 0，例如00009312345。小B还有一个素数P。现在，小 B 提出了 M 个询问，每个询问求 S 的一个子串中有多少子串是 P 的倍数（0 也是P 的倍数）。

例如 S为0077时，其子串 007有6个子串：0,0,7,00,07,007；显然0077的子串007有6个子串都是素

数7的倍数。

输入格式

第一行一个整数：P。

第二行一个串：S。

第三行一个整数：M。

接下来M行，每行两个整数 fr,to，表示对S 的子串S[fr…to]的一次询问。

注意：S的最左端的数字的位置序号为 1；例如S为213567，则S[1]为 2，S[1…3]为 213。N,M<=100000，P为素数

输出格式

输出M行，每行一个整数，第 i行是第 i个询问的答案。

样例输入

11

121121

3

1 6

1 5

1 4

样例输出

5

3

2

提示

对于30%的数据: n,m<=1000

对于60%的数据: n<=10000,m<=1000

对于100%的数据：n,m<=100000,p是素数

判断一个字串是否能被P整除，容易想到求出该串的后缀模P的值，然后当$P\neq2\&\&P\neq5$时，子串$[L,R]$能被P整除当且仅当后缀$L$和$R+1$模P的值相等。因此可以离散化后用莫队维护模P的cnt值。然后组合数求方案即可。

当P等于2或5时需要特判。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 100005
#define ll long long
using namespace std;
struct node{int l,r,id;}K[N];
ll P,n,m,D[N],A[N],B[N],cnt[N],S,id[N],Ans[N],ans,L,R;
char s[N];
bool cmp(node a,node b)
{
	if(id[a.l]==id[b.l])return a.r<b.r;
	return id[a.l]<id[b.l];
}
void UD1(ll k,int d)
{
	if(d==1)
	{
		if(k<L)
		{
			if(D[k]%2)ans+=cnt[0],cnt[1]++;
			else ans+=++cnt[0];
		}
		else
		{
			if(D[k]%2)cnt[1]++;
			else cnt[0]++,ans+=(R-L+2);
		}
	}
	else
	{
		if(k==L)
		{
			if(D[k]%2)ans-=cnt[0],cnt[1]--;
			else ans-=cnt[0],cnt[0]--;
		}
		else
		{
			if(D[k]%2)cnt[1]--;
			else ans-=(R-L+1),cnt[0]--;
		}
	}
}
void UD2(ll k,int d)
{
	if(d==1)
	{
		if(k<L)
		{
			if(D[k]%5)ans+=cnt[0],cnt[1]++;
			else ans+=++cnt[0];
		}
		else
		{
			if(D[k]%5)cnt[1]++;
			else cnt[0]++,ans+=(R-L+2);
		}
	}
	else
	{
		if(k==L)
		{
			if(D[k]%5)ans-=cnt[0],cnt[1]--;
			else ans-=cnt[0],cnt[0]--;
		}
		else
		{
			if(D[k]%5)cnt[1]--;
			else ans-=(R-L+1),cnt[0]--;
		}
	}
}
void UD(ll k,int d)
{
	if(P==2){UD1(k,d);return;}
	if(P==5){UD2(k,d);return;}
	k=A[k];
	ans-=cnt[k]*(cnt[k]-1)>>1;
	cnt[k]+=d;
	ans+=cnt[k]*(cnt[k]-1)>>1;
}
int main()
{
	//freopen("data.in","r",stdin);
	//freopen("zj.out","w",stdout);
	ll i,j,k,tmp;
	scanf("%lld",&P);
	scanf("\n%s",&s[1]);
	n=strlen(s+1);
	S=sqrt(n);
	for(i=n,tmp=1;i>=1;i--,tmp=tmp*10%P)
	{
		D[i]=s[i]-48;
		A[i]=(A[i+1]+D[i]*tmp%P)%P;
		B[i]=A[i];
	}
	B[n+1]=0;
	sort(B+1,B+n+2);
	for(i=1;i<=n+1;i++)A[i]=lower_bound(B+1,B+n+2,A[i])-B;
	for(i=1;i<=n+1;i++)id[i]=i/S;
	scanf("%lld",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&K[i].l,&K[i].r);
		K[i].id=i;
		if(P!=2&&P!=5)K[i].r++;
	}
	sort(K+1,K+m+1,cmp);
	L=1;R=0;
	for(i=1;i<=m;i++)
	{
		while(R<K[i].r)UD(R+1,1),R++;
		while(R>K[i].r)UD(R,-1),R--;
		while(L<K[i].l)UD(L,-1),L++;
		while(L>K[i].l)UD(L-1,1),L--;
		Ans[K[i].id]=ans;
	}
	for(i=1;i<=m;i++)printf("%lld\n",Ans[i]);
}