[bzoj3131]淘金[sdoi2013][数位DP]

求出每个数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

 #include <bits/stdc++.h> using namespace std; const long long MOD=1e9+; long long    a[],Len;
 long long    f[][][],g[];
 long long    n,K;
 vector<long long> vec; struct cmp
 {
     bool    operator()(const pair<long long,long long> temp1,
             const pair<long long,long long> temp2)
     {
         return (long long)g[temp1.first]*g[temp1.second]<
             (long long)g[temp2.first]*g[temp2.second];
     }
 }; void    Init()
 { long long temp=n; while(temp) { a[++Len]=temp%; temp/=; } return ; } void    Dfs(const long long cur,const long long step,const long long mul)
 {
     vec.push_back(mul); if(step==Len)return ;
     for(long long i=cur;i<=;++i) Dfs(i,step+,mul*i);
     return ;
 } int main()
 {
     scanf("%lld%lld",&n,&K);     //INIT mul->vec_____________________________________________________
     Init(); Dfs(,,);
     //------------------------------------------------------------------     vec.push_back();     sort(vec.begin(),vec.end());
     vec.erase(unique(vec.begin(),vec.end()),vec.end());     //Dp start Hear_____________________________________________________
     f[][][]=;
     for(long long i=;i<=Len;++i)
     for(long long j=;j<(long long)vec.size();++j)
     for(long long k=;k<=;++k)
     {
         if(f[i][j][k])         for(long long x=i==?:;x<=;++x)
         //Zero is allowed at the beginning only if len=1
         {
             long long temp=
                 lower_bound(vec.begin(),vec.end(),vec[j]*x)-
                 vec.begin();
             f[i+][temp][(k+x)>a[i+]]+=f[i][j][k];
         }
     }
     //------------------------------------------------------------------     //Calc g[i]_________________________________________________________
     for(long long i=;i<(long long)vec.size();++i)
     {
         for(long long j=;j<=Len-;++j)
             g[i]+=f[j][i][]+f[j][i][];         g[i]+=f[Len][i][]; //Not to exceed N
     }
     //------------------------------------------------------------------     //Get_Ans_with_Priority_Queue_______________________________________
     long long    Ans=;     typedef    pair<long long,long long> PII;
     priority_queue<PII,vector<PII>,cmp>Q;     sort(g,g+vec.size(),greater<long long>());
     Q.push(make_pair(,));     while(!Q.empty() && K)
     {
         pair<long long,long long> t=Q.top(); Q.pop();         Ans=(Ans+g[t.first]*g[t.second])%MOD;
         if(!(--K)) break;         if(t.first!=t.second)
         {
             Ans=(Ans+g[t.first]*g[t.second])%MOD;             if(!(--K)) break;
             Q.push(make_pair(t.first+,t.second));
         }         if(t.first==) Q.push(make_pair(t.first,t.second+));//QAQ
     }
     //------------------------------------------------------------------     printf("%lld\n",Ans);
     return ;
 }