首页 > 代码库 > 大数(bzoj 4542)
大数(bzoj 4542)
/* 想了半天莫队,不知道咋转移,需要动下脑子。 有一个很显然的结论是如果(l,r)是P的倍数,那么s[l...n]%P=s[r+1...n]%P。 根据这个东西,我们预处理出所有的后缀%P的余数,接下里就是查询区间内相同得数对数量,就很好转移了。 有一点,当P=2或5时,不否和上面的情况,需单独讨论。 */ #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<map> #define N 200010 #define lon long long using namespace std; lon n,m,p,len,a[N],b[N],cnt[N],ans[N];char s[N]; map<lon,lon> mp; struct node{ lon l,r,id; bool operator<(node s1) const{ if(l/len==s1.l/len) return r<s1.r; return l/len<s1.l/len; } }q[N]; int main(){ scanf("%lld%s%lld",&p,s+1,&m); n=strlen(s+1);len=(lon)sqrt(n); if(p!=2&&p!=5){ lon bt=1; for(lon i=n;i;i--){ bt=bt*10%p; a[i]=(a[i+1]+(s[i]-‘0‘)*bt)%p; b[i]=a[i]; } sort(b+1,b+n+1); for(lon i=1;i<=n+1;i++) mp[b[i]]=i; for(lon i=1;i<=n+1;i++) a[i]=mp[a[i]]; for(lon i=1;i<=m;i++){ scanf("%lld%lld",&q[i].l,&q[i].r); q[i].id=i;q[i].r++; } sort(q+1,q+m+1); lon l=1,r=0,cur=0; for(lon i=1;i<=m;i++){ while(r<q[i].r) ++r,cur+=cnt[a[r]]++; while(l>q[i].l) --l,cur+=cnt[a[l]]++; while(l<q[i].l) cur-=--cnt[a[l]],l++; while(r>q[i].r) cur-=--cnt[a[r]],r--; ans[q[i].id]=cur; } for(lon i=1;i<=m;i++) printf("%lld\n",ans[i]); } else { for(lon i=1;i<=n;i++) if(!((s[i]-‘0‘)%p)) cnt[i]=cnt[i-1]+1,a[i]=a[i-1]+i; else cnt[i]=cnt[i-1],a[i]=a[i-1]; for(lon i=1;i<=m;i++){ lon l,r; scanf("%lld%lld",&l,&r); printf("%lld\n",a[r]-a[l-1]-(cnt[r]-cnt[l-1])*(l-1)); } } return 0; }
Description
小 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的倍数。
Input
第一行一个整数:P。第二行一个串:S。第三行一个整数:M。接下来M行,每行两个整数 fr,to,表示对S 的
子串S[fr…to]的一次询问。注意:S的最左端的数字的位置序号为 1;例如S为213567,则S[1]为 2,S[1…3]为 2
13。N,M<=100000,P为素数
Output
输出M行,每行一个整数,第 i行是第 i个询问的答案。
Sample Input
11
121121
3
1 6
1 5
1 4
121121
3
1 6
1 5
1 4
Sample Output
5
3
2
//第一个询问问的是整个串,满足条件的子串分别有:121121,2112,11,121,121。
3
2
//第一个询问问的是整个串,满足条件的子串分别有:121121,2112,11,121,121。
大数(bzoj 4542)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。