首页 > 代码库 > BZOJ4542 [HNOI2016] 大数
BZOJ4542 [HNOI2016] 大数
【问题描述】
小 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]为 2
13。N,M<=100000,P为素数
【输出格式】
输出M行,每行一个整数,第 i行是第 i个询问的答案。
【输入样例】
11
121121
3
1 6
1 5
1 4
【输出样例】
5
3
2
【样例解释】
第一个询问问的是整个串,满足条件的子串分别有:121121,2112,11,121,121。
【数据规模】
N,M<=100000
正解:莫队算法+特判
1 #include <iostream> 2 #include <iomanip> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <cstring> 9 #include <map> 10 #define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout) 11 #define RG register 12 #define ull unsigned long long 13 const int N = 150000; 14 15 using namespace std; 16 17 map <ull,ull> Map; 18 19 ull gi(){ 20 char ch=getchar();ull x=0; 21 while(ch<‘0‘ || ch>‘9‘)ch=getchar(); 22 while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();} 23 return x; 24 } 25 26 char ch[N]; 27 ull yu[N],rt[N],jl[N],da[N],xh[N],sum[N]; 28 ull sq; 29 30 struct date{ 31 int l,r,i; 32 bool operator < (const date &a) const{ 33 if (a.l/sq==l/sq) return a.r>r; 34 return a.l/sq>l/sq; 35 } 36 }f[N],t[N]; 37 38 bool cmp(const date &a,const date &b){ 39 if (a.r==b.r) return a.l<b.l; 40 return a.r<b.r; 41 } 42 43 void put(ull x) 44 { 45 int num = 0; char c[20]; 46 while(x) c[++num] = (x%10)+48, x /= 10; 47 while(num) putchar(c[num--]); 48 putchar(‘\n‘); 49 } 50 51 int main(){ 52 File("number"); 53 ull p=gi();scanf("%s",ch); 54 int q=gi();RG int i,l,r;ull ans=0;ull j; 55 int h=strlen(ch);sq=sqrt(h*1.0); 56 for (i=1; i<=q; i++) f[i]=(date){gi(),gi(),i}; 57 if (p!=2 && p!=5){ 58 for (i=1; i<=q; i++) f[i].r++; 59 j=1;yu[h+1]=0; 60 for (i=h-1; i>=0; i--){ 61 j=j*10%p; 62 rt[i+1]=yu[i+1]=(yu[i+2]+(ch[i]-‘0‘)*j)%p; 63 }h++; 64 sort(rt+1,rt+h+1); 65 sort(f+1,f+q+1); 66 for (i=1; i<=h; i++) Map[rt[i]]=i; 67 for (i=1; i<=h; i++) yu[i]=Map[yu[i]]; 68 l=f[1].l,r=l-1;ans=0; 69 for (i=1; i<=q; i++){ 70 while(l>f[i].l) ans+=jl[yu[--l]]++; 71 while(r<f[i].r) ans+=jl[yu[++r]]++; 72 while(l<f[i].l) ans-=--jl[yu[l++]]; 73 while(r>f[i].r) ans-=--jl[yu[r--]]; 74 da[f[i].i]=ans; 75 } 76 }else{ 77 for (i=1; i<=h; i++){ 78 yu[i]=(ch[i-1]-‘0‘)%p; 79 xh[i]=xh[i-1]+(yu[i]==0?1:0); 80 sum[i]=sum[i-1]+(yu[i]==0?i:0); 81 } 82 for (i=1; i<=q; i++) 83 da[i]=sum[f[i].r]-sum[f[i].l-1]-(f[i].l-1)*(xh[f[i].r]-xh[f[i].l-1]); 84 } 85 for (i=1; i<=q; i++) 86 if (da[i]) put(da[i]); 87 else printf("0\n"); 88 return 0; 89 }
BZOJ4542 [HNOI2016] 大数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。