bzoj 4542: [Hnoi2016]大数

在p!=2且p!=5的情况下,x*10^k%p=0，则x%p=0,所以可以维护后缀和%p的值，然后用莫队求区间内相同的数的对数。 p=2 or p=5 最后一位决定%p之后的值，yy一下即可

   
   
    
      
    
    
      
    
    
      
    
    
      
    
    
      
    
    
      
    
    
      
    
    
      
    
    
      
    
    
      
    
    
      
    
   
   #include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<map>#include<cmath>#define ll long long#define inf 1e9#define eps 1e-8#define N 100010using namespace std;struct QQ { int l,r,id;} q[N];map<ll,int> mp;ll s[N],ans[N];int pos[N],c[N];char st[N];ll md,sum=0;int n,m;?void ycl(){ if (md!=2&&md!=5) { ll mi=1; for (int i=n;i;i--) { s[i]=(s[i+1]+mi*(st[i]-'0'))%md; mi=mi*10%md; } int cnt=0; for (int i=1;i<=n+1;i++) { if (mp[s[i]]==0) mp[s[i]]=++cnt; s[i]=mp[s[i]]; } } else for (int i=1;i<=n;i++) s[i]=((st[i]-'0')%md==0); int k=sqrt(n); for (int i=1;i<=n;i++) pos[i]=(i-1)/k+1;}?bool cmp (QQ a,QQ b) { return pos[a.l]==pos[b.l]?a.r<b.r:a.l<b.l;}?void solve_25(){ int l=1,r=0,ps=0; sum=0; for (int i=1;i<=m;i++) { while (q[i].l<l) { l--; ps+=s[l]; sum+=ps; } while (r<q[i].r) { r++; if (s[r]) sum+=r-l+1,ps++; } while (l<q[i].l) { sum-=ps; ps-=s[l]; l++; } while (q[i].r<r) { if (s[r]) sum-=r-l+1,ps--; r--; } ans[q[i].id]=sum; }}?void add(int x){ sum+=c[s[x]]; c[s[x]]++;}?void del(int x){ c[s[x]]--; sum-=c[s[x]];}?void solve_p(){ int l=1,r=0; sum=0; for (int i=1;i<=m;i++) { q[i].r++; while (q[i].l<l) { l--; add(l); } while (r<q[i].r) { r++; add(r); } while (l<q[i].l) { del(l); l++; } while (q[i].r<r) { del(r); r--; } ans[q[i].id]=sum; }}?int main(){ scanf("%lld",&md); scanf("%s",st+1); n=strlen(st+1); ycl(); scanf("%d",&m); for (int i=1;i<=m;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i;} sort(q+1,q+m+1,cmp); if (md==2||md==5) solve_25(); else solve_p(); for (int i=1;i<=m;i++) printf("%lldn",ans[i]);  return 0;}

（编辑：PHP编程网 - 黄冈站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!