求出每个数i可以被转移到的数目$f[i]$，则点$(i,j)$中的金子数目为$f[i]*f[j]$，我们就可以用优先队列求解前$k$大。

首先所有的积数目在$10^4$左右，可以先Dfs搜索出所有的数值，然后离散化。

设$f[i][j][k]$表示i位数，积为$j$(离散)，当前枚举位是否小于$n$的第$i$位，枚举第$i+1$位数转移即可。

　　$f[i][j][k] \longrightarrow f[i+1][num[j]*x][(k+x)>a[i+1]]$

　　用$g[i]$表示乘积$i$的种类数

　　【学习】http://www.cnblogs.com/lidaxin/p/5234975.html

1 #include 
     
        2   3 using namespace std;  4   5 const long long MOD=1e9+7;  6   7 long long    a[15],Len;  8 long long    f[15][410000][2],g[410000];  9 long long    n,K; 10 vector
      
        vec; 11  12 struct cmp 13 { 14     bool    operator()(const pair
       
         temp1, 15             const pair
        
          temp2) 16     { 17         return (long long)g[temp1.first]*g[temp1.second]< 18             (long long)g[temp2.first]*g[temp2.second]; 19     } 20 }; 21  22 void    Init() 23 { long long temp=n; while(temp) { a[++Len]=temp%10; temp/=10; } return ; } 24  25 void    Dfs(const long long cur,const long long step,const long long mul) 26 { 27     vec.push_back(mul); if(step==Len)return ; 28     for(long long i=cur;i<=9;++i) Dfs(i,step+1,mul*i); 29     return ; 30 } 31  32 int main() 33 { 34     scanf("%lld%lld",&n,&K); 35  36     //INIT mul->vec_____________________________________________________ 37     Init(); Dfs(1,0,1); 38     //------------------------------------------------------------------ 39      40     vec.push_back(0); 41  42     sort(vec.begin(),vec.end()); 43     vec.erase(unique(vec.begin(),vec.end()),vec.end()); 44  45     //Dp start Hear_____________________________________________________ 46     f[0][1][0]=1; 47     for(long long i=0;i<=Len;++i) 48     for(long long j=0;j<(long long)vec.size();++j) 49     for(long long k=0;k<=1;++k) 50     { 51         if(f[i][j][k]) 52  53         for(long long x=i==0?0:1;x<=9;++x) 54         //Zero is allowed at the beginning only if len=1 55         { 56             long long temp= 57                 lower_bound(vec.begin(),vec.end(),vec[j]*x)- 58                 vec.begin(); 59             f[i+1][temp][(k+x)>a[i+1]]+=f[i][j][k]; 60         } 61     } 62     //------------------------------------------------------------------ 63  64     //Calc g[i]_________________________________________________________ 65     for(long long i=0;i<(long long)vec.size();++i) 66     { 67         for(long long j=1;j<=Len-1;++j) 68             g[i]+=f[j][i][0]+f[j][i][1]; 69  70         g[i]+=f[Len][i][0]; //Not to exceed N 71     } 72     //------------------------------------------------------------------ 73  74  75     //Get_Ans_with_Priority_Queue_______________________________________ 76     long long    Ans=0; 77  78     typedef    pair
         
           PII; 79     priority_queue
          
           
            ,cmp>Q; 80 81 sort(g,g+vec.size(),greater
            
             ()); 82 Q.push(make_pair(1,1)); 83 84 while(!Q.empty() && K) 85 { 86 pair
             
               t=Q.top(); Q.pop(); 87 88 Ans=(Ans+g[t.first]*g[t.second])%MOD; 89 if(!(--K)) break; 90 91 if(t.first!=t.second) 92 { 93 Ans=(Ans+g[t.first]*g[t.second])%MOD; 94 95 if(!(--K)) break; 96 Q.push(make_pair(t.first+1,t.second)); 97 } 98 99 if(t.first==1) Q.push(make_pair(t.first,t.second+1));//QAQ100 }101 //------------------------------------------------------------------102 103 printf("%lld\n",Ans);104 return 0;105 }