[BZOJ4542][Hnoi2016]大數(shù)（莫隊+數(shù)學(xué)相關(guān)）

2019-11-06 06:04:23

字體：大中小

供稿：網(wǎng)友

題目描述

傳送門

題解

設(shè)f(i)表示[i..n]組成的十進(jìn)制數(shù)在模p意義下的值那么f(i)-f(j)(j>i)就表示了[i..j-1]這一段區(qū)間表示的十進(jìn)制數(shù)擴大10的若干次冪之后在模p意義下的值如果不考慮質(zhì)數(shù)2和5的話，擴大10的若干次冪是不應(yīng)響結(jié)果的，因為剩余的質(zhì)數(shù)都不是10的約數(shù) 那么如果要統(tǒng)計區(qū)間[l..r]有多少個子串滿足是p的倍數(shù)的話，只需要統(tǒng)計f(l)..f(r+1)這些數(shù)中有多少對數(shù)相同就行了將f(i)離散化之后搞一個計數(shù)器然后直接莫隊就行了然后特判一下2和5的情況，因為擴大了10的若干次冪，相當(dāng)于加了若干個質(zhì)因子2和5，不能像上面那樣求但是其實2和5的情況更簡單若p=2/5，如果某一個位上的數(shù)是能整除p，那它的后綴都是p的倍數(shù)都可以計算然后搞一個前綴和每次查詢的時候減一下就行了

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define LL long long#define N 100005char s[N];LL p,suf[N],lsh[N],ans;int n,m,LSH,block,num[N],cnt[N];struct data{int l,r,id;LL ans;}q[N];int find(int x){ int l=1,r=LSH,mid,ans; while (l<=r) { mid=(l+r)>>1; if (x>=lsh[mid]) ans=mid,l=mid+1; else r=mid-1; } return ans;}int cmp(data a,data b){ return num[a.l]<num[b.l]||(num[a.l]==num[b.l]&&a.r<b.r);}void modui(int l,int r,int opt){ for (int i=l;i<=r;++i) { int x=suf[i]; ans-=(LL)cnt[x]*(cnt[x]-1)/2; cnt[x]+=opt; ans+=(LL)cnt[x]*(cnt[x]-1)/2; }}int main(){ scanf("%lld",&p); if (p==2||p==5) { scanf("%s",s+1);n=strlen(s+1); for (int i=1;i<=n;++i) if ((s[i]-'0')%p==0) cnt[i]=1,suf[i]=(LL)i; for (int i=1;i<=n;++i) cnt[i]+=cnt[i-1],suf[i]+=suf[i-1]; scanf("%d",&m); for (int i=1;i<=m;++i) { int l,r;scanf("%d%d",&l,&r); ans=suf[r]-suf[l-1]-(LL)(l-1)*(cnt[r]-cnt[l-1]);