BZOJ 4542 大数

发表于 | 更新于

Link

Solution

如果上式==0==0，那么可以得到 也==0==0。 这样的话当 的时候，反推，用后缀的差是否为零来判断s[l:r]s[l:r]是否 剩下的特殊处理就好了

Code

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
#include "lucida"
using std::sort;
using std::unique;
using std::lower_bound;
const int MAXN=100000+11;
int n,bn[MAXN],m;
int64 Ans[MAXN],P;
char S[MAXN];	
struct Opt {
	int l,r,id;
	bool operator <(const Opt &x) const {
		return bn[l]!=bn[x.l]?bn[l]<bn[x.l]:r<x.r;
	}
}p[MAXN];
namespace Mo {
	int64 cAns;
	int cnt[MAXN],c[MAXN];
	int64 suf[MAXN],nums[MAXN];
	int64 C2(int n) {
		return n<2?0:(int64)n*(n-1)>>1;
	}
	void Modify(int pos,int d) {
		cAns-=C2(cnt[c[pos]]);
		cnt[c[pos]]+=d;
		cAns+=C2(cnt[c[pos]]);
	}
	void Solve() {
		int bsz=sqrt(n+0.5);
		for(int i=1;i<=n;++i)
			bn[i]=(i-1)/bsz+1;
		int nc=0;
		for(int i=n,pw=1;i;--i,pw=(int64)pw*10%P) {
			suf[i]=((int64)(S[i]-'0')*pw+suf[i+1])%P;
			nums[++nc]=suf[i];
		}
		nums[++nc]=0;sort(nums+1,nums+1+nc);
		nc=unique(nums+1,nums+1+nc)-nums-1;
		for(int i=1;i<=n+1;++i) c[i]=lower_bound(nums+1,nums+1+nc,suf[i])-nums;
		sort(p+1,p+1+m);
		for(int i=1;i<=m;++i) ++p[i].r;
		//区间内有多少种同颜色的点
		for(int i=p[1].l;i<=p[1].r;++i)
			Modify(i,1);
		Ans[p[1].id]=cAns;
		for(int i=2;i<=m;++i) {
			for(int t=p[i-1].l-1;t>=p[i].l;--t) Modify(t,1);
			for(int t=p[i-1].r+1;t<=p[i].r;++t) Modify(t,1);
			for(int t=p[i-1].l;t<=p[i].l-1;++t) Modify(t,-1);
			for(int t=p[i-1].r;t>=p[i].r+1;--t) Modify(t,-1);
			Ans[p[i].id]=cAns;
		}
	}
}
namespace Sp {
	int cnt[MAXN];
	int64 sum[MAXN];
	void Solve() {
		for(int i=1;i<=n;++i) {
			cnt[i]=cnt[i-1]+((S[i]-'0')%P==0);
			sum[i]=sum[i-1]+((S[i]-'0')%P==0)*i;//(i-1)??
		}
		for(int i=1;i<=m;++i)
			Ans[i]=(sum[p[i].r]-sum[p[i].l-1])-(int64)(cnt[p[i].r]-cnt[p[i].l-1])*(p[i].l-1);
	}
}
int main() {
	freopen("input","r",stdin);
	is>>P>>(S+1)>>m;n=strlen(S+1);
	for(int i=1;i<=m;++i) {
		is>>p[i].l>>p[i].r;
		p[i].id=i;
	}
	if(10%P) Mo::Solve(); 
	else Sp::Solve();
	for(int i=1;i<=m;++i)
		os<<Ans[i]<<'\n';
	return 0;
}