[bzoj4542][HNOI2016]大数
题目大意给定字符串 式子转化如果对[l,r]询问那么答案相当于 #include<cstdio>
#include<algorithm>
#include<cmath>
#include<ctime>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn=100000+10;
int belong[maxn],s[maxn],cnt[maxn],ans[maxn];
ll num[maxn],b[maxn];
struct dong{
int l,r,id;
} ask[maxn];
bool operator <(dong a,dong b){
if (belong[a.l]<belong[b.l]) return 1;
else if (belong[a.l]==belong[b.l]&&a.r<b.r) return 1;
else return 0;
}
int i,j,k,l,n,m,c,now;
ll t,p,q;
char ch;
ll qsc(ll x,ll y){
if (!y) return 0;
ll t=qsc(x,y/2); t=(t+t)%p; if (y%2) t=(t+x)%p; return t; } ll qsm(ll x,int y){ if (!y) return 1; ll t=qsm(x,y/2); t=qsc(t,t); if (y%2) t=qsc(t,x); return t; } void gcd(ll a,ll b,ll &x,ll &y){ if (!b){ x=1; y=0; return; } else{ gcd(b,a%b,x,y); swap(x,y); y-=x*(a/b);
}
}
ll getny(ll a,ll b){
ll x,y;
gcd(a,b,x,y);
x=(x%b+b)%b;
return x;
}
int main(){
//freopen("number13.in","r",stdin);freopen("answer.out","w",stdout);
scanf("%lld",&p);
ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
s[n=1]=ch-'0';
while (1){
ch=getchar();
if (ch<'0'||ch>'9') break;
s[++n]=ch-'0';
}
s[++n]=0;
c=floor(sqrt(n));
fo(i,1,n) belong[i]=(i-1)/c+1;
scanf("%d",&m);
fo(i,m) scanf("%d%d",&ask[i].l,&ask[i].r),ask[i].r++,ask[i].id=i;
//printf("%dn",clock());
sort(ask+1,ask+m+1);
if (p!=2&&p!=5){
t=1;
fd(i,1){
b[i]=num[i]=(ll)(num[i+1]+(ll)s[i]*t%p)%p;
t=t*10%p;
}
sort(b+1,b+n+2);
l=unique(b+1,b+n+2)-b-1;
fo(i,n) num[i]=lower_bound(b+1,b+l+1,num[i])-b;
}
//printf("%dn",clock());
l=1;r=0;
fo(i,m){
while (l<ask[i].l){
if (p==2){
now-=t;
if (s[l]%2==0) t--;
}
else if (p==5){
now-=t;
if (s[l]%5==0) t--;
}
else{
cnt[num[l]]--;
now-=cnt[num[l]];
}
l++;
}
while (l>ask[i].l){
l--;
if (p==2){
if (s[l]%2==0) t++;
now+=t;
}
else if (p==5){
if (s[l]%5==0) t++;
now+=t;
}
else{
now+=cnt[num[l]];
cnt[num[l]]++;
}
}
while (r>ask[i].r){
if (p==2){
if (s[r]%2==0) now-=(r-l+1),t--;
}
else if (p==5){
if (s[r]%5==0) now-=(r-l+1),t--;
}
else{
cnt[num[r]]--;
now-=cnt[num[r]];
}
r--;
}
while (r<ask[i].r){
r++;
if (p==2){
if (s[r]%2==0) now+=(r-l+1),t++;
}
else if (p==5){
if (s[r]%5==0) now+=(r-l+1),t++;
}
else{
now+=cnt[num[r]];
cnt[num[r]]++;
}
}
ans[ask[i].id]=now;
}
fo(i,m) printf("%dn",ans[i]);
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |