首页 > 代码库 > 【BZOJ】4542: [Hnoi2016]大数
【BZOJ】4542: [Hnoi2016]大数
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4542
给定一个由数字构成的字符串${S_{1,2,3,...,n}}$,一个正素数$P$，每次询问给定一对$l$,$r$求：
$${\sum_{l=1}^{n}\sum_{r=i}^{n}\left [ \sum _{i=l}^{r}S[i]*10^{r-i} \,\,\,\,MOD\,\,\,\,P=0 \right ]}$$
即以位置$x$开头的后缀的数字$%P$之后的值为$val[x]$，如果一个数字对应区间${[l,r]}$它$%p$为$0$的充要条件为${val[l]=val[r-1]}$，然后套上莫队算法，离散化$val$数组，就变成了经典的查询一个区间相同数字的点对有多少个。
注意：$p=2,5$的情况中并不满足以上性质，记一下前缀和然后特判即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 300100 10 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 12 llg n,m,p,quan[maxn],tail,val[maxn],len,se[maxn],KUAI; 13 long long ans,Ans[maxn],jisuan1[maxn],jisuan2[maxn]; 14 char s[maxn]; 15 struct Q_ 16 { 17 llg l,r,num; 18 }ask[maxn]; 19 20 bool cmp(const Q_&a,const Q_&b) {if (a.l/KUAI==b.l/KUAI) return a.r<b.r; else return a.l/KUAI<b.l/KUAI; } 21 22 llg find(llg x) 23 { 24 llg l=1,r=len,wz=-1,mid; 25 while (l<=r) 26 { 27 mid=(l+r)>>1; 28 if (quan[mid]<=x) {wz=mid; l=mid+1;}else {r=mid-1;} 29 } 30 return wz; 31 } 32 33 void solve() 34 { 35 cin>>m; 36 for(int i=1;i<=n;i++) 37 { 38 jisuan1[i]=jisuan1[i-1]; jisuan2[i]=jisuan2[i-1]; 39 if( (s[i]-‘0‘)%p==0 ) 40 { 41 jisuan1[i]++; 42 jisuan2[i]+=i; 43 } 44 45 } 46 for(int i=1;i<=m;i++) 47 { 48 llg x,y; 49 scanf("%lld%lld",&x,&y); 50 printf("%lld\n",jisuan2[y]-jisuan2[x-1] - (x-1)*(jisuan1[y]-jisuan1[x-1])); 51 } 52 } 53 54 void init() 55 { 56 cin>>p; 57 scanf("%s",s+1); 58 n=strlen(s+1); 59 KUAI=sqrt(n)+1; 60 if (p==5 || p==2) return ; 61 cin>>m; 62 for (llg i=1;i<=m;i++) scanf("%lld%lld",&ask[i].l,&ask[i].r),ask[i].r++,ask[i].num=i; 63 sort(ask+1,ask+m+1,cmp); 64 llg C=1; 65 tail=1;quan[1]=0; 66 for (llg i=n;i>=1;i--) 67 { 68 val[i]=val[i+1]+C*(s[i]-‘0‘); 69 val[i]%=p; 70 quan[++tail]=val[i]; 71 C*=10; C%=p; 72 } 73 sort(quan+1,quan+tail+1); 74 len=unique(quan+1,quan+tail+1)-(quan+1); 75 for (llg i=1;i<=n+1;i++) val[i]=find(val[i]); 76 } 77 78 int main() 79 { 80 yyj("number"); 81 init(); 82 if (p==2 || p==5) {solve(); return 0;} 83 84 llg l=ask[1].l,r=ask[1].r; 85 for (llg i=l;i<=r;i++) 86 { 87 ans+=se[val[i]]; 88 se[val[i]]++; 89 } 90 Ans[ask[1].num]=ans; 91 for (llg k=2;k<=m;k++) 92 { 93 llg nl=ask[k].l,nr=ask[k].r; 94 if (nr>r) 95 { 96 for (llg i=r+1;i<=nr;i++) 97 { 98 ans+=se[val[i]]; 99 se[val[i]]++;100 }101 }102 if (nr<r)103 {104 for (llg i=r;i>nr;i--)105 {106 ans-=se[val[i]]-1;107 se[val[i]]--;108 }109 }110 if (l<nl)111 {112 for (llg i=l;i<nl;i++)113 {114 ans-=se[val[i]]-1;115 se[val[i]]--;116 }117 }118 if (l>nl)119 {120 for (llg i=l-1;i>=nl;i--)121 {122 ans+=se[val[i]];123 se[val[i]]++;124 }125 }126 Ans[ask[k].num]=ans;127 l=nl,r=nr;128 }129 for (llg i=1;i<=m;i++) printf("%lld\n",Ans[i]); 130 return 0;131 }
【BZOJ】4542: [Hnoi2016]大数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。