HNOI2016 大数(number)
发布时间:2020-12-14 01:52:29 所属栏目:大数据 来源:网络整理
导读:分析 首先,我们要知道取模的几个性质: 设 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;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |