C++11(clang++ 3.9) 解法, 执行用时: 45ms, 内存消耗: 3136K, 提交时间: 2019-04-06 12:39:14

#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std;
typedef long long LL;
const int N = 4*1e5;
const int MOD = 1e9+7;

LL f[15][N][2],num[N],siz[N];
int tot,K,a[15],len; LL n;

struct Node{
    int x,y; LL v;
    Node(int x,int y):x(x),y(y) { v=siz[x]*siz[y]; }
    bool operator < (const Node& rhs) const{
        return v<rhs.v;
    }
};
priority_queue<Node> q;
bool cmp(const LL& x,const LL& y) {
    return x>y;
}

void dfs(int now,int dep,LL mul) {
    if(dep==len) num[tot++]=mul;
    else {
        if(!mul) return ;
        for(int i=now;i<10;i++)
            dfs(i,dep+1,mul*i);
    }
}

int main() {
    scanf("%lld%d",&n,&K);
    LL tmp=n;
    while(n) {
        a[++len]=n%10;
        n/=10;
    }
    num[++tot]=0;
    dfs(0,0,1);
    sort(num+1,num+tot+1);
    tot=unique(num+1,num+tot+1)-num-1;
    f[0][2][0]=1;
    FOR(i,0,len) FOR(j,1,tot) FOR(k,0,1) if(f[i][j][k])
        for(int x=i==0?0:1;x<10;x++) {                            //只允许长度为 1 的0存在
            int r=lower_bound(num+1,num+tot+1,num[j]*x)-num;
            f[i+1][r][(k+x)>a[i+1]]+=f[i][j][k];
        }
    FOR(i,1,tot) {
        FOR(j,1,len-1)
            siz[i]+=f[j][i][0]+f[j][i][1];
        siz[i]+=f[len][i][0];
    }
    sort(siz+1,siz+tot+1,cmp);
    q.push(Node(2,2));
    int ans=0;
    while(!q.empty() && K) {
        Node u=q.top(); q.pop();
        ans=(ans+u.v)%MOD;
        if(!(--K)) break;
        if(u.x!=u.y) {
            ans=(ans+u.v)%MOD;
            if(!(--K)) break;
            q.push(Node(u.x+1,u.y));
        }
        if(u.x==2) q.push(Node(u.x,u.y+1));
    }
    printf("%d",ans);
    return 0;
}