题解 P5842 【[SCOI2012]Blinker 的仰慕者】

· · 题解

Update on 2020.5.31：极大简化了代码，跑的飞快

小蒟蒻的第一篇题解，望大家支持，如有排版格式问题还请见谅。

此题比较复杂，做的话需要先熟悉数位dp的基本套路，我们慢慢分析。

看到 “各位数字之积” 应该可以想到这是数位dp题，那么最朴素的想法就是 f(i,j) 表示前 i 位数各位数字之积为 j 时的答案，j 最大10^{18}，无法通过。

考虑到 K 为 1-9 这些数字的乘积（我们先忽略0），K的质因子就只有 2,3,5,7 四个，因此我们可以用四个下标 a , b , c , d 来表示 j ，即 j=2^a * 3^b * 5^c * 7^d ,但是把四个参数都写到dp数组里的话状态数还是有点大，达到了 1e8 的级别。

为了减少复杂度我们先预处理出 10^{18} 所有以内所有可能的 j （j=2^a * 3^b * 5^c * 7^d） ,它可以很暴力（反正数很少），如下：

    int lim2=59,lim3=37,lim5=25,lim7=21;
    ll fac2[60],fac3[60],fac5[60],fac7[60];
    fac2[0]=fac3[0]=fac5[0]=fac7[0]=1;
    fac[0]=1;
    for(int i=1;i<=lim2;i++)fac2[i]=fac2[i-1]*2;
    for(int i=1;i<=lim3;i++)fac3[i]=fac3[i-1]*3;
    for(int i=1;i<=lim5;i++)fac5[i]=fac5[i-1]*5;
    for(int i=1;i<=lim7;i++)fac7[i]=fac7[i-1]*7;
    for(int i=1;i<=18;i++)fac[i]=fac[i-1]*10;
    maxk=fac[18];
    for(int i=1;i<=18;i++)fac[i]%=mod;
    for(int i=0;i<=lim2;i++)
        for(int j=0;j<=lim3&&fac2[i]*fac3[j]<=maxk;j++)
            for(int k=0;k<=lim5&&fac2[i]*fac3[j]*fac5[k]<=maxk;k++)
                for(int l=0;l<=lim7&&fac2[i]*fac3[j]*fac5[k]*fac7[l]<=maxk;l++)
                    num[++kcnt]=fac2[i]*fac3[j]*fac5[k]*fac7[l];
    sort(num+1,num+kcnt+1);

为了转移方便，某个 j 与1-9中的某数运算的结果在数表num中的位置我们也需要知道，预处理出来，p_{0-3} 对应着2,3,5,7。

    for(int i=1;i<=kcnt;i++)to[i][1]=i;
    for(int i=0;i<=3;i++)
        for(int j=1;j<=kcnt;j++)
            if(num[j]%p[i]==0)to[j][p[i]]=id(num[j]/p[i]);
    for(int i=4;i<=9;i++)
    {
        if(i==p[0]||i==p[1]||i==p[2]||i==p[3])continue;
        for(int j=1;j<=kcnt;j++)to[j][i]=getto(j,i);
    }

其中 to(i,j) 表示数表中第 i 个数除以 j 的结果在数表中的位置（注意是除不是乘，原因下面讲）id函数使用的stl的二分查找，getto是质因数分解求to的过程，如to(i,4)=to(to(i,2),2) 。 代码如下：

int id(ll x)
{
    return lower_bound(num+1,num+kcnt+1,x)-num;
}
int getto(int x,int k)
{
    for(int i=0;i<=3;i++)
        while(k%p[i]==0)
        {
            k/=p[i];
            x=to[x][p[i]];
        }
    return x;
}

然后我们的dp状态就可以设计为 f(i,j) 表示前 i 位当前乘积为 j 的答案数，因为如果没有数的大小限制，且没有前导零的影响，f(i,j)的值就只与最终数位的乘积K有关系。我们把f(i,j)的含义改一下，表示到了第 i 位，还需要的数位乘积为 j 的答案，那么 f(i,j)的值与K也没有了关系（把K当初始值来看）。我们求答案用到 f 的时候已经有小于上界和无前导零的条件，这两维不用考虑。

我们再关注一下这个题要求什么：满足题意数的和。如果求个数的话就很简单了，和怎么求呢？我们还要加入一个数组g，f,g的最终含义：f(i,j)表示到了第 i 位，还需要的数位乘积为 j 时的方案数： g(i,j)表示到了第 i 位，还需要的数位乘积为 j 时可以填的数的和（中间两维我略了）。这个 g 指的数是从第 i 位开始计的，比如i=3，后三位可以填123,213,321这三个数,，那么f的值为3，g 的值即为123+213+321

f(i,j),g(i,j)$如何转移呢？$f$ 的值可以直接从下一位累加，假设第 $i$ 位我们填了a，后面还有3位，$g$ 计算的和即为形如aXXX这样的数的和，这个XXX每有一种方案, $g$ 就加上$1000a

而后面这些可能的XXX的总和恰是下一位的 g 要所表示的，XXX的方案数则由下一位的 f 表示，那么这个预先dp就可以写出了（边界值按f,g的定义很好考虑, fac(i)为10^i：

void dp(int k,int rest)
{
    if(!k)
    {
        f[k][rest]=(rest==1);
        g[k][rest]=0;
        return;
    }
    if(f[k][rest]!=-1)return;
    ll rf=0,rg=0;
    int a1,a2;
    for(int i=9;i>=1;i--)
    {
        a1=k-1;
        a2=(i==0)?rest:to[rest][i];
        if(!a2)continue;
        dp(a1,a2);
        rf+=f[a1][a2];
        rg=(rg+i*f[a1][a2]*fac[k-1]+g[a1][a2])%mod;
    }
    f[k][rest]=rf%mod;
    g[k][rest]=rg;
    return;
}

剩余的数位乘积是减少的，to在这里就用上了（这就是为什么to处理的是除）。

需要 f,g 的值时调用这个dp：

if(f[k][rest]==-1)dp(k,rest);

那么对于输入的A,B,K，先转化成前缀相减：

cout<<((solve(r)-solve(l-1))%mod+mod)%mod<<endl;

在上界的限制下dfs每一位填什么，并传递当前前缀值，如果满足已经小于上界、没有前导零影响了，直接返回答案，计算方法与 g 的推导类似，可以把当前的前缀值pre看做我们刚才讨论 g 时的a。dfs代码如下：

ll dfs(int k,int low,int zero,int rest,ll pre)
{
    if(!rest)return 0;
    if(low&(!zero))
    {
        if(f[k][rest]==-1)dp(k,rest);
        return (pre*fac[k]%mod*f[k][rest]+g[k][rest])%mod;
    }
    if(!k)return pre*(rest==1);
    ll res=0;
    for(int i=low?9:a[k];i>=(!zero);i--)
        res+=dfs(k-1,low|(i<a[k]),zero&(i==0),(i==0)?rest:to[rest][i],(pre*10+i)%mod);
    return res;
}

这个题做完了？似乎我们还忽略了零。。。

如果K=0 ,问题可以看做求在A到B中所有至少有一位为零的数的和，（和上面那些比这还不简单）与f,g的定义类似，f0(i,j,k,l)表示到了第 i 位 是（1）否（0）小于上界值，是（1）否（0）有前导零， 前面已经有 l 个零时的填的方案数，g0 表示填的数的和，注意前导零。

void dp0(int k,int low,int zero,int cnt0)
{
    if(!k)
    {
        f0[k][low][zero][cnt0]=(cnt0>0);
        g0[k][low][zero][cnt0]=0;
        return;
    }
    if(f0[k][low][zero][cnt0]!=-1)return;
    ll rf=0,rg=0;
    int b1,b2,b3,b4;
    for(int i=low?9:a[k];i>=0;i--)
    {
        b1=k-1;
        b2=low|(i<a[k]);
        b3=zero&(i==0);
        b4=cnt0+((!zero)&(i==0));
        dp0(b1,b2,b3,b4);
        rf=(rf+f0[b1][b2][b3][b4])%mod;
        rg=(rg+i*f0[b1][b2][b3][b4]*fac[k-1]%mod+g0[b1][b2][b3][b4])%mod;
    }
    f0[k][low][zero][cnt0]=rf;
    g0[k][low][zero][cnt0]=rg;
    return;
}

还有一些细节如判断K是否可以被2,3,5,7质因数分解等不一一赘述了，看完整代码吧，少用些取模运算速度提升很大。

感觉自己写的复杂度很高，常数很大，有可优化之处还望各位dalao赐教qwq。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#define ll long long
using namespace std;
const int mod=20120427;
int kcnt;
int to[70000][10],a[20],p[4]={2,3,5,7};
ll l,r,K,maxk;
ll fac[20],num[70000],f[20][70000],g[20][70000];
ll f0[20][2][2][20],g0[20][2][2][20];
int id(ll x)
{
    return lower_bound(num+1,num+kcnt+1,x)-num;
}
int getto(int x,int k)
{
    for(int i=0;i<=3;i++)
        while(k%p[i]==0)
        {
            k/=p[i];
            x=to[x][p[i]];
        }
    return x;
}
void dp(int k,int rest)
{
    if(!k)
    {
        f[k][rest]=(rest==1);
        g[k][rest]=0;
        return;
    }
    if(f[k][rest]!=-1)return;
    ll rf=0,rg=0;
    int a1,a2;
    for(int i=9;i>=1;i--)
    {
        a1=k-1;
        a2=(i==0)?rest:to[rest][i];
        if(!a2)continue;
        dp(a1,a2);
        rf+=f[a1][a2];
        rg=(rg+i*f[a1][a2]*fac[k-1]+g[a1][a2])%mod;
    }
    f[k][rest]=rf%mod;
    g[k][rest]=rg;
    return;
}
void init()
{ 
    int lim2=59,lim3=37,lim5=25,lim7=21;
    ll fac2[60],fac3[60],fac5[60],fac7[60];
    fac2[0]=fac3[0]=fac5[0]=fac7[0]=1;
    fac[0]=1;
    for(int i=1;i<=lim2;i++)fac2[i]=fac2[i-1]*2;
    for(int i=1;i<=lim3;i++)fac3[i]=fac3[i-1]*3;
    for(int i=1;i<=lim5;i++)fac5[i]=fac5[i-1]*5;
    for(int i=1;i<=lim7;i++)fac7[i]=fac7[i-1]*7;
    for(int i=1;i<=18;i++)fac[i]=fac[i-1]*10;
    maxk=fac[18];
    for(int i=1;i<=18;i++)fac[i]%=mod;
    for(int i=0;i<=lim2;i++)
        for(int j=0;j<=lim3&&fac2[i]*fac3[j]<=maxk;j++)
            for(int k=0;k<=lim5&&fac2[i]*fac3[j]*fac5[k]<=maxk;k++)
                for(int l=0;l<=lim7&&fac2[i]*fac3[j]*fac5[k]*fac7[l]<=maxk;l++)
                    num[++kcnt]=fac2[i]*fac3[j]*fac5[k]*fac7[l];
    //cout<<kcnt<<endl;
    sort(num+1,num+kcnt+1);
    for(int i=1;i<=kcnt;i++)to[i][1]=i;
    for(int i=0;i<=3;i++)
        for(int j=1;j<=kcnt;j++)
            if(num[j]%p[i]==0)to[j][p[i]]=id(num[j]/p[i]);
    for(int i=4;i<=9;i++)
    {
        if(i==p[0]||i==p[1]||i==p[2]||i==p[3])continue;
        for(int j=1;j<=kcnt;j++)to[j][i]=getto(j,i);
    }
    memset(f,-1,sizeof(f));
    return;
}
ll check(ll x)
{
    for(int i=0;i<=3;i++)
        while(x%p[i]==0)x/=p[i];
    return x;
}
ll dfs(int k,int low,int zero,int rest,ll pre)
{
    if(!rest)return 0;
    if(low&(!zero))
    {
        if(f[k][rest]==-1)dp(k,rest);
        return (pre*fac[k]%mod*f[k][rest]+g[k][rest])%mod;
    }
    if(!k)return pre*(rest==1);
    ll res=0;
    for(int i=low?9:a[k];i>=(!zero);i--)
        res+=dfs(k-1,low|(i<a[k]),zero&(i==0),(i==0)?rest:to[rest][i],(pre*10+i)%mod);
    return res;
}
void dp0(int k,int low,int zero,int cnt0)
{
    if(!k)
    {
        f0[k][low][zero][cnt0]=(cnt0>0);
        g0[k][low][zero][cnt0]=0;
        return;
    }
    if(f0[k][low][zero][cnt0]!=-1)return;
    ll rf=0,rg=0;
    int b1,b2,b3,b4;
    for(int i=low?9:a[k];i>=0;i--)
    {
        b1=k-1;
        b2=low|(i<a[k]);
        b3=zero&(i==0);
        b4=cnt0+((!zero)&(i==0));
        dp0(b1,b2,b3,b4);
        rf=(rf+f0[b1][b2][b3][b4])%mod;
        rg=(rg+i*f0[b1][b2][b3][b4]*fac[k-1]+g0[b1][b2][b3][b4])%mod;
    }
    f0[k][low][zero][cnt0]=rf;
    g0[k][low][zero][cnt0]=rg;
    return;
}
ll solve(ll x)
{
    int len=0;
    while(x)
    {
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,1,id(K),0);
}
ll solve0(ll x)
{
    int len=0;
    while(x)
    {
        a[++len]=x%10;
        x/=10;
    }
    memset(f0,-1,sizeof(f0));
    dp0(len,0,1,0);
    return g0[len][0][1][0];
}
int main()
{
    int T;
    init();
    cin>>T;
    while(T--)
    {
        cin>>l>>r>>K;
        if(!K)
        {
            cout<<((solve0(r)-solve0(l-1))%mod+mod)%mod<<endl;
            continue;
        }
        ll x=check(K);
        if(x!=1)
        {
            cout<<0<<endl;
            continue;
        }
        cout<<((solve(r)-solve(l-1))%mod+mod)%mod<<endl;
    }
    return 0;
}