题意：
有一个$n imes n$的网格，初始时每个格子上有一个金币，行列编号为$[1,n]$。
然后发生了一次操作，原来位于$(x,y)$的金币移动到了$(f_x ,f_y )$，其中$f_x$为x在十进制下各位数字的乘积。
在操作之后你可以取K个格子里的金币，问最多能取多少个，对$10^{9}+7$取模。
$nleq 10^{12},Kleq min(n^{2},10^{5})$。
题解：
挺水的一道题。洛谷这个难度评级是咋回事啊QAQ
由于$1-9$只有4个质因子（只要有0肯定就不行），所以目测满足$f_x >0$的x应该不会太多。
既然这是一篇题解，我们就考虑证明一下：
设十进制下上界是k位，那么要算的就近似于从$1-9$里可以重复的选k个数字的方案数。
发现这就是可重组合模型：从非空集合$X={1,2,cdots,n}$中取r个元素，可以重复取某个元素。
该模型的方案数为${n+r-1choose r}={n+r-1choose n-1}$，计算可得大约$num=10000$个。
小奥理解：将r个一样的东西分到n个不同的盒子里，可以有空盒子$ ightarrow$将r+n个一样的东西分到n个不同的盒子里，不能有空盒子$ ightarrow$插板法，在r+n-1个空里插n-1个板$ ightarrow{n+r-1choose n-1}$。
回到原题，我们只需要爆搜出所有有值的$f_x =y$，再令$c_y$表示有多少个x满足$f_x =y$，然后优先队列维护一下即可。
这个$c_y$需要数位dp求，看似复杂度是$O(num imes 状态数 imes 转移数)$的，但其实不是。
由于我们的状态是$dp(n,n_2 ,n_3 ,n_5 ,n_7 )$表示已经填了前n位，每个质因子还要填$n_i$个的合法数字个数，那么每次求完一个y其实是不用清空dp数组的。
跑优先队列的时候注意不要在排序的时候取模，这会让本来单调的东西变得不单调。
复杂度$O(120num)$。
套路：
- 取模时：注意如果当前算的东西对后面有影响就不要取模。
- 可重组合数：从非空集合$X={1,2,cdots,n}$中可以重复地取r个元素$ ightarrow{n+r-1choose r}$。
- dp的两种设状态方式：第一种是“已经做了”，第二种是“还需要做”。
代码：
#include<bits/stdc++.h> #define maxn 200005 #define maxm 500005 #define inf 0x7fffffff #define mod 1000000007 #define ll long long #define rint register ll #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; unordered_map<ll,ll> id,vis[maxn]; ll A[maxn],B[maxn][4],C[maxn],dig[13],nxt[10][4]; ll dp[15][40][26][18][15]; struct node{ ll x,y; bool operator<(const node b)const{return C[x]*C[y]<C[b.x]*C[b.y];} }; priority_queue<node> q; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline void dfs1(ll x,ll n2,ll n3,ll n5,ll n7,ll n){ if(x>n || id[x]) return; A[++A[0]]=x,id[x]=A[0]; B[A[0]][0]=n2,B[A[0]][1]=n3,B[A[0]][2]=n5,B[A[0]][3]=n7; dfs1(x*2,n2+1,n3,n5,n7,n),dfs1(x*3,n2,n3+1,n5,n7,n); dfs1(x*5,n2,n3,n5+1,n7,n),dfs1(x*7,n2,n3,n5,n7+1,n); } inline ll dfs2(ll n,ll n2,ll n3,ll n5,ll n7,ll ise,ll isz){ if(n2<0 || n3<0 || n5<0 || n7<0) return 0; if(!n) return (!n2)&&(!n3)&&(!n5)&&(!n7)&&(!isz); if(dp[n][n2][n3][n5][n7]!=-1 && !ise && !isz) return dp[n][n2][n3][n5][n7]; ll res=0; if(isz) res+=dfs2(n-1,n2,n3,n5,n7,0,isz); for(ll i=1;i<=(ise?dig[n]:9);i++){ ll nn2=n2-nxt[i][0],nn3=n3-nxt[i][1],nn5=n5-nxt[i][2],nn7=n7-nxt[i][3]; res+=dfs2(n-1,nn2,nn3,nn5,nn7,ise&(i==dig[n]),0); } if(!ise && !isz) dp[n][n2][n3][n5][n7]=res; return res; } inline bool cmp(ll a,ll b){return a>b;} int main(){ ll n=read(),K=read(),x=n; while(x) dig[++dig[0]]=x%10,x/=10; dfs1(1,0,0,0,0,n); nxt[2][0]=1,nxt[3][1]=1,nxt[4][0]=2,nxt[5][2]=1; nxt[6][0]=nxt[6][1]=1,nxt[7][3]=1,nxt[8][0]=3,nxt[9][1]=2; memset(dp,-1,sizeof(dp)); for(ll i=1;i<=A[0];i++) C[i]=dfs2(dig[0],B[i][0],B[i][1],B[i][2],B[i][3],1,1); sort(C+1,C+1+A[0],cmp); q.push((node){1,1}); ll ans=0; while(K){ node tp=q.top(); q.pop(); if(vis[tp.x][tp.y]) continue; K--,vis[tp.x][tp.y]=1,ans+=C[tp.x]*C[tp.y]%mod,ans%=mod; q.push((node){tp.x+1,tp.y}); q.push((node){tp.x,tp.y+1}); } printf("%lld ",ans); return 0; }