BZOJ 4542: [Hnoi2016]大數

突然覺得整場省選我都是處于腦殘狀态

這才是兩天中最簡單的題

首先p為2,5的時候特判一下，所有以p的倍數結尾的大數都是p的倍數

然後令a[i]為以i為左端點的字尾數模p的結果，顯然number(l,r)=(a[l]-a[r+1])/(10^(n-r))

即a[l]-a[r+1]=number(l,r)*10^(n-r)，顯然10的任意次方與p互質，是以要想number(l,r)是p的倍數，那麼a[l]==a[r+1]，于是問題就是求區間[l,r+1]内相等的數對個數，上莫隊就好了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=100000+5;
typedef long long ll;
ll hash[N],a[N];
int b[N],c[N],d[N];
struct Query{
	int l,r,id;
	bool operator < (const Query &x)const{
		return b[l]==b[x.l]?r<x.r:b[l]<b[x.l];
	}
}q[N];
char s[N];
ll res[N];
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
int main(){
	//freopen("a.in","r",stdin);
	ll p;scanf("%lld",&p);
	scanf("%s",s+1);int n=strlen(s+1);
	if(p==2||p==5){
		rep(i,1,n)if((s[i]-'0')%p==0)a[i]=i,b[i]=1;
		rep(i,1,n)a[i]+=a[i-1],b[i]+=b[i-1];
		int m;scanf("%d",&m);
		while(m--){
			int l,r;scanf("%d%d",&l,&r);
			printf("%lld\n",a[r]-a[l-1]-(ll)(l-1)*(b[r]-b[l-1]));
		}
	}else{
		ll ten=1;
		per(i,n,1)a[i]=(a[i+1]+(s[i]-'0')*ten)%p,ten=ten*10%p;
		n++;rep(i,1,n)hash[i]=a[i];
		sort(hash+1,hash+1+n);
		rep(i,1,n)d[i]=lower_bound(hash+1,hash+1+n,a[i])-hash;
		int block=sqrt(n+0.5);
		rep(i,1,n)b[i]=(i-1)/block;
		int m;scanf("%d",&m);
		rep(i,1,m)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i,q[i].r++;
		sort(q+1,q+1+m);
		int ql=1,qr=0;ll ans=0;
		rep(i,1,m){
			while(qr<q[i].r)ans+=c[d[++qr]]++;
			while(q[i].l<ql)ans+=c[d[--ql]]++;
			while(ql<q[i].l)ans-=--c[d[ql++]];
			while(q[i].r<qr)ans-=--c[d[qr--]];
			res[q[i].id]=ans;
		}
		rep(i,1,m)printf("%lld\n",res[i]);
	}
	return 0;
}
           

論智商不線上的危害