题目连接：http://www.lydsy.com/JudgeOnline/problem.php?id=3131
首先可以想到先算出一维的，再拓展到二维。
我们设g[i]表示各位数字乘积为i的数字个数(<=n)，然后可以用堆/优先队列算出二维的前k大。
现在关键是如何求g[i]。
我一开始也不会~(≧▽≦)/~啦啦啦，但实际上所有乘积总个数只有2e5多(我也不知道为什么有题解说是1e4。。。可能是我错了吧)，将乘积离散化，然后就可以进行数位DP了。具体如下：设f[i][j][k]表示当前算到第i位，乘积下标为j，到目前为止是否大于n。转移时要二分乘积的位置，所以复杂度是位数*乘积个数*log乘积个数*2
注：stl是个好东西啊，unique真方便~
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<iostream> #include<string> #include<ctime> #include<queue> #include<map> #include<set> #include<vector> #define LL long long using namespace std; const int N=400010,mod=1e9+7; struct node { int x,y; LL z; bool operator < (const node &x) const{return z<x.z;} }; priority_queue<node>q; LL n,f[15][N][2],g[N],a[N]; int k,cnt,num[15],len; LL read() {LL d=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') d=(d<<3)+(d<<1)+c-48,c=getchar(); return d*f;} void judge(){freopen(".in","r",stdin); freopen(".out","w",stdout);} void dfs(int k,int l,LL now) { if (l>len) {a[++cnt]=now; return;} for (int i=k;i<10;i++) dfs(i,l+1,now*i); } bool cmp(LL a,LL b){return a>b;} node make(int x,int y) { node res; res.x=x; res.y=y; res.z=g[x]*g[y]; return res; } int main() { //judge(); n=read(); k=read(); for (;n;n/=10) num[++len]=n%10; a[cnt=1]=0; dfs(1,1,1); sort(a+1,a+1+cnt); cnt=unique(a+1,a+1+cnt)-a-1; f[0][2][0]=1; for (int i=0;i<=len;i++) for (int j=1;j<=cnt;j++) for (int k=0;k<=1;k++) if (f[i][j][k]) for (int l=i?1:0;l<10;l++) { int pjy=lower_bound(a+1,a+1+cnt,a[j]*l)-a; f[i+1][pjy][k+l>num[i+1]]+=f[i][j][k]; } for (int i=1;i<=cnt;i++) { for (int j=1;j<len;j++) g[i]+=f[j][i][0]+f[j][i][1]; g[i]+=f[len][i][0]; } sort(g+1,g+1+cnt,cmp); LL ans=0; q.push(make(2,2)); while (!q.empty()) { node ljj=q.top(); q.pop(); ans=(ans+ljj.z)%mod; if (--k==0) break; if (ljj.x!=ljj.y) { ans=(ans+ljj.z)%mod; if (--k==0) break; q.push(make(ljj.x+1,ljj.y)); } if (ljj.x==2) q.push(make(ljj.x,ljj.y+1)); } printf("%d",ans); return 0; }