BZOJ AC900题纪念~~

 

若K>0，则

设f[i][j]表示i位数字，积为j的数字的个数

g[i][j]表示i位数字，积为j的数字的和

DP+Hash预处理

查询时枚举LCP然后统计贡献

若K=0，则

设f[i][j][k][l]表示已知前i位，乘积是否不为0，是否等于x，是否有数字的数字的个数

g[i][j][k][l]表示已知前i位，乘积是否不为0，是否等于x，是否有数字的数字的和

数位DP即可

 

#include
     
      typedef long long ll;const int P=20120427,H=1000037,M=66062;int a[19],len,i,j,k,t,T,g[H],nxt[M],ed;ll n,l,r,K,tmp,pow[19],fin,v[M];inline int get(ll u){  int x=u%H,i=g[x];  for(;i;i=nxt[i])if(v[i]==u)return i;  return v[++ed]=u,nxt[ed]=g[x],g[x]=ed;}inline int ask(ll u){  for(int i=g[u%H];i;i=nxt[i])if(v[i]==u)return i;  return 0;}namespace Subtask1{int f[19][M],g[19][M];void init(){  f[0][get(1)]=1;  for(i=0;i<18;i++)for(j=1;j<=ed;j++)for(k=1;k<=9;k++){    if(v[j]*k>1000000000000000000LL)break;    (f[i+1][t=get(v[j]*k)]+=f[i][j])%=P;    (g[i+1][t]+=g[i][j]*10+f[i][j]*k)%=P;  }}inline ll cal(ll x,ll K){  ll ans=0,pre=0,mul=1;  for(len=0,tmp=x;tmp;a[++len]=tmp%10,tmp/=10);  for(i=len;i;i--){    if(!a[i])break;    for(j=1;j
      
       0][i==a[1]][i>0]++,g[1][i>0][i==a[1]][i>0]+=i;  for(i=1;i
       
        <2;j++){    for(k=0;k<=9;k++)(f[i+1][k>0][0][k>0]+=f[i][j][0][0])%=P,(g[i+1][k>0][0][k>0]+=g[i][j][0][0]*10%P+f[i][j][0][0]*k%P)%=P;    for(k=0;k<=9;k++)(f[i+1][j&&k>0][0][1]+=f[i][j][0][1])%=P,(g[i+1][j&&k>0][0][1]+=g[i][j][0][1]*10%P+f[i][j][0][1]*k%P)%=P;    for(k=0;k<=a[i+1];k++)(f[i+1][j&&k>0][k==a[i+1]][1]+=f[i][j][1][1])%=P,(g[i+1][j&&k>0][k==a[i+1]][1]+=g[i][j][1][1]*10%P+f[i][j][1][1]*k%P)%=P;  }  return g[len][0][0][1];}}int main(){  for(pow[0]=i=1;i<19;i++)pow[i]=pow[i-1]*10;  Subtask1::init();  scanf("%d",&T);  while(T--){    scanf("%lld%lld%lld",&l,&r,&K);    if(K)fin=(Subtask1::cal(r+1,K)-Subtask1::cal(l,K))%P;else fin=(Subtask2::cal(r+1)-Subtask2::cal(l))%P;    while(fin<0)fin+=P;    printf("%lld\n",fin);  }  return 0;}