小Z在玩一个叫做《淘金者》的游戏。游戏的世界是一个二维坐标。X轴、Y轴坐标范围均为1..N。初始的时候，所有的整数坐标点上均有一块金子，共N*N块。
一阵风吹过，金子的位置发生了一些变化。细心的小Z发现，初始在(i，j)坐标处的金子会变到(f(i)，fIj))坐标处。其中f(x)表示x各位数字的乘积，例如f(99)=81，f(12)=2，f(10)=0。如果金子变化后的坐标不在1..N的范围内，我们认为这块金子已经被移出游戏。同时可以发现，对于变化之后的游戏局面，某些坐标上的金子数量可能不止一块，而另外一些坐标上可能已经没有金子。这次变化之后，游戏将不会再对金子的位置和数量进行改变，玩家可以开始进行采集工作。
小Z很懒，打算只进行K次采集。每次采集可以得到某一个坐标上的所有金子，采集之后，该坐标上的金子数变为0。
现在小Z希望知道，对于变化之后的游戏局面，在采集次数为K的前提下，最多可以采集到多少块金子？
答案可能很大，小Z希望得到对1000000007(10^9+7)取模之后的答案。
共一行，包含两介正整数N，K。
一个整数，表示最多可以采集到的金子数量。
N < = 10^12 ,K < = 100000
对于100%的测试数据：K < = N^2
求出每个数i可以被转移到的数目f[i]，则点(i，j)中的金子数目为f[i]*f[j]，就可以用优先队列求解前k大
首先所有的积数目在1e4左右，可以先dfs搜索出所有的数值，然后离散化
设f[i][j][k]表示i位数，积为j，到当前枚举位是否大于n，枚举第i+1位数转移
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 #define ll long long 7 using namespace std; 8 const int N=4*1e5,mo=1e9+7; 9 ll n,f[15][N][2],num[N],sz[N]; 10 int tot,K,ans,len,a[15]; 11 struct node 12 { 13 int x,y; ll v; 14 node(int x,int y):x(x),y(y) { v=sz[x]*sz[y]; } 15 bool operator < (const node& a) const{ return v<a.v; } 16 }; 17 priority_queue<node> Q; 18 bool cmp(ll x,ll y) { return x>y; } 19 void dfs(int now,int dep,ll mul) { if (dep==len) num[tot++]=mul; else if (mul) for (int i=now;i<10;i++) dfs(i,dep+1,mul*i); } 20 int main() 21 { 22 scanf("%lld%d",&n,&K); ll tmp=n; 23 while (n) a[++len]=n%10,n/=10; 24 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; 25 for (int i=0,r;i<=len;i++) 26 for (int j=1;j<=tot;j++) 27 for (int k=0;k<=1;k++) 28 if (f[i][j][k]) 29 for (int x=i==0?0:1;x<10;x++) 30 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]; 31 for (int i=1;i<=tot;i++) 32 { 33 for (int j=1;j<=len-1;j++) sz[i]+=f[j][i][0]+f[j][i][1]; 34 sz[i]+=f[len][i][0]; 35 } 36 sort(sz+1,sz+tot+1,cmp),Q.push(node(2,2)); 37 while (!Q.empty()&&K) 38 { 39 node u=Q.top(); Q.pop(),ans=(ans+u.v)%mo; 40 if (!(--K)) break; 41 if (u.x!=u.y) 42 { 43 ans=(ans+u.v)%mo; 44 if (!(--K)) break; 45 Q.push(node(u.x+1,u.y)); 46 } 47 if (u.x==2) Q.push(node(u.x,u.y+1)); 48 } 49 printf("%d",ans); 50 }
原文：https://www.cnblogs.com/Comfortable/p/11216636.html