HNOI2016 大数(number)
发布时间：2021-03-19 15:14:12 所属栏目：大数据 来源：网络整理
导读：分析 首先，我们要知道取模的几个性质： 设 p=a+b ， q=a*b 1. p%x=(a%x+b%x)%x 2. q%x=(a%x*b%x)%x 知道这两个性质之后，我们首先输入进要模的数 x 和字符串 s ，处理出一个后缀数组 m ，和一个 po 数组， m[i] 表示字符串中从前往后数的第 i 位到结尾所组
|
分析首先，我们要知道取模的几个性质：
可以知道，设 m[i]组成的数是p'，m[j]组成的数是a'，k组成的数是b'，则可知b'*10^(n-j)+a'=p'，那么m[i]=(k*po[n-j])%x+m[j]，因为要让k=0所以就要满足m[i]==m[j]。但是在这里需要注意一下，由于当x=2,5的时候m[i]==m[j]是（基本上）始终满足的，因为10^o除了o=0以外都可以整除2,5所以要特判一下。不过由于数据中没有模数为2,5的情况，所以偷懒没写- -。 于是做好这个之后，离散化一下，求解就很简单了。我们可以定义一个 l和r，给它们附一个初值，然后慢慢地挪到询问的位置，用桶来存每个m出现的次数，很容易可以得到答案。 但是这样还不够快。就要用到莫队的思想了。 我们将每一个 l,r看做二维平面上的点，那么要让“挪过去”的复杂度最小，也就是连接每个点的曼哈顿距离总和最小。简单不严谨的写法就是，将这些点按横坐标排序，分块，然后每个块中按纵坐标排序，然后进行答案的计算。 其余的细节就给大家思考了。 代码如下#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=200003;
struct query{
int l,r,id;
ll ans=0;
}q[maxn];
bool cmp1(query a,query b){
return a.l<=b.l?1:0;
}
bool cmp2(query a,query b){
return a.r<=b.r?1:0;
}
bool cmp3(query a,query b){
return a.r>=b.r?1:0;
}
bool cmp4(query a,query b){
return a.id<b.id?1:0;
}
char a[maxn];
ll c[maxn],m[maxn],po[maxn],mo;
int buk[maxn],n,lim,k;
int main(){
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
scanf("%lld",&mo);
scanf("%s",&a);
scanf("%d",&lim);
k=sqrt(lim);
for(int i=1;i<=lim;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+lim+1,cmp1);
bool flag=0;
for(int i=1;i<=lim;i+=k,flag^=1)
if(flag)sort(q+i,q+min(k+i,lim+1),cmp3);
else sort(q+i,cmp2);
n=strlen(a);
m[n]=0;po[0]=1%mo;
for(int i=n;i>0;i--){
po[n-i+1]=(po[n-i]*(10%mo))%mo;
m[i]=(m[i+1]+(((a[i-1]-'0')%mo)*(po[n-i]%mo)))%mo;
c[i]=m[i];
}
sort(c+1,c+n+2);
int left=1,right=2;c[1]=m[1];
while(right<=n+1){
while(right<=n+1&&c[right]==c[left])right++;
if(right<=n+1)c[++left]=c[right];
}
int l,mid;
for(int i=1;i<=n+1;i++){
l=1,r=left+1;
while(l+1<r){
mid=(l+r)/2;
if(c[mid]<=m[i])l=mid;
else r=mid;
}
m[i]=l;
}
ll ql,qr,ans=0;
l=1,r=2;
for(int i=1;i<=lim;i++){
ql=q[i].l,qr=q[i].r;
while(l<ql)
l++,buk[m[l]]--,ans-=buk[m[l]];
while(l>=ql)
ans+=buk[m[l]],buk[m[l]]++,l--;
while(r>qr)
r--,buk[m[r]]--,ans-=buk[m[r]];
while(r<=qr+1)
ans+=buk[m[r]],buk[m[r]]++,r++;
q[i].ans=ans;
}
sort(q+1,cmp4);
for(int i=1;i<=lim;i++)printf("%lldn",q[i].ans);
return 0;
}
（编辑：济源站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
