首页 > 代码库 > BZOJ2757: [SCOI2012]Blinker的仰慕者
BZOJ2757: [SCOI2012]Blinker的仰慕者
这题……我一般数位dp都是直接用一个dp把所有东西算完,然而……多组询问每次重新dp会T……然后只好先预处理再查询,然后还搞不了k=0,只好再单独写一个dp……烦死了……
k!=0时,数位的乘积总共就几万种,离散化再预处理转移。f[i][j]表示前i位,乘积为j。k==0时,f[i][2][2][2][2]表示第i位,是否卡下界,是否卡上界,乘积是否为0,是否全是前导0。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int p=20120427; const int M=20; const int N=6e4; int n,q,z1[N][10],z2[N][10]; ll x,y,k,e[M]={1},z3[N],f[M][N][2]; int sol(int r1,ll r2){ int m=0,r3[M],r4=0; for(ll i=r2;i;i/=10) r3[m++]=i%10; for(int i=1;i<m;++i) r4=(r4+f[i][r1][1])%p; for(int i=m-1;~i;--i){ ll r5=r2/e[i+1]*10; for(int j=1;j<r3[i];++j) if(~z2[r1][j]){ ll*r6=f[i][z2[r1][j]]; r4=(r4+r6[1]+(r5+j)*e[i]%p*r6[0])%p; } r1=z2[r1][r3[i]]; if(!~r1)break; } return r4; } int cal(ll i){ return lower_bound(z3,z3+n,i)-z3; } namespace ns1{ int m,z1[M],z2[M],f[M][2][2][2][2][2]; void sol(){ for(--x,++y,m=0;y;++m){ z1[m]=x%10,x/=10; z2[m]=y%10,y/=10; } for(int i=m;i<M;++i) z1[i]=z2[i]=0; memset(f,0,sizeof f); f[m][1][1][0][1][0]=1; for(int a=m-1;~a;--a) for(int b=1;~b;--b) for(int c=1;~c;--c){ int u=b?z1[a]:0,v=c?z2[a]:9; for(int d=1;~d;--d){ int(*s)[2]=f[a+1][b][c][d]; for(int e=u;e<=v;++e){ int(*t)[2][2]=f[a][b&e==z1[a]][c&e==z2[a]]; (t[d|!e][0][0]+=s[0][0])%=p; (t[d|!e][0][1]+=s[0][1]*10+e*s[0][0])%=p; (t[0][!e][0]+=s[1][0])%=p; (t[0][!e][1]+=e*s[1][0])%=p; } } } printf("%d\n",f[0][0][0][1][0][1]); } } int main(){ for(int i=1;i<M;++i) e[i]=e[i-1]*10; const ll v=16e16; for(ll a=1;a<v;a*=2) for(ll b=a;b<v;b*=3) for(ll c=b;c<v;c*=5) for(ll d=c;d<v;d*=7)z3[n++]=d; sort(z3,z3+n); memset(z1,-1,sizeof z1); memset(z2,-1,sizeof z2); for(int j=0;j<n;++j) for(int i=9;i;--i) if(z3[j]*i<v) z2[z1[j][i]=cal(z3[j]*i)][i]=j; f[0][0][0]=1; for(int i=0;i<18;++i) for(int j=0;j<n;++j){ ll*s=f[i][j]; if(!s[0])continue; s[0]%=p; for(int k=9;k;--k) if(~z1[j][k]){ ll*t=f[i+1][z1[j][k]]; t[0]+=s[0]; (t[1]+=s[1]+k*e[i]%p*s[0])%=p; } } scanf("%d",&q); while(q--){ scanf("%lld%lld%lld",&x,&y,&k); if(!k)ns1::sol(); else if(k>=v)puts("0"); else{ int j=cal(k); if(z3[j]!=k)puts("0"); else printf("%d\n",(sol(j,y+1)-sol(j,x)+p)%p); } } }
BZOJ2757: [SCOI2012]Blinker的仰慕者
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。