题目概述

有 $n\times n$ 的网格，每个格子有 $1$ 块金子，现在处在 $(i,j)$ 的会变到 $(f(i),f(j))$ ，其中 $f(i)$ 表示 $i$ 十进制表示下所有位的乘积。可以采集 $K$ 次，问最多能够采集多少。

解题报告

我们想要知道的是多少（记为 $C_i$ ）行（列）最终会变到 $i$ 身上，那么 $(i,j)$ 格子的金子个数就是 $C_iC_j$ ，这个很明显可以数位DP，$f_{i,j,0/1}$ 表示做到第 $i$ 位得到 $j$ 这个乘积的方案以及有没有达到上限，则 $C_i=f_{1,i,0}+f_{1,i,1}$ 。

但是不可能存 $j$ 啊，$j$ 太大了。实际上因为素因子只有 $2,3,5,7$ ，所以有用的 $j$ 其实不多，估算一下只有 $2\cdot 10^5$ 的级别，不过当你挖出来之后发现只有 $15000$ 个……

采集 $K​$ 次的话直接用堆+贪心搞就行了。

示例程序

#include<cstdio>
#include<algorithm>
#include<map>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=14672,maxk=200000,maxl=12,MOD=1e9+7;

LL n;int K,tot,nxt[maxn+5][10],a[maxl+5];LL tem[maxn+5],f[maxl+5][maxn+5][2],C[maxn+5];
int que[maxn+5];map<LL,int> ID;int pos[maxn+5],si;pair<LL,int> Heap[maxk+5];int ans;

void Dfs(LL x) {if (x>n||ID.count(x)) return;tem[ID[x]=++tot]=x;Dfs(x*2);Dfs(x*3);Dfs(x*5);Dfs(x*7);}
#define Push(x) (Heap[++si]=(x),push_heap(Heap+1,Heap+1+si))
#define Pop() (pop_heap(Heap+1,Heap+1+si--))
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%lld%d",&n,&K);Dfs(1);LL N=n;do a[++a[0]]=N%10,N/=10; while (N);f[a[0]+1][ID[1]][1]=1;
    for (int i=1;i<=tot;i++) for (int j=1;j<10;j++) if (ID.count(tem[i]*j)) nxt[i][j]=ID[tem[i]*j];
    for (int i=a[0];i;i>1?f[i--][ID[1]][0]++:i--)
        for (int fl=0;fl<2;fl++)
            for (int j=1;j<=tot;j++)
                for (int k=1,MAX=fl?a[i]:9;k<=MAX;k++)
                    if (nxt[j][k]) f[i][nxt[j][k]][fl&&k==MAX]+=f[i+1][j][fl];
    for (int i=1;i<=tot;i++) C[i]=-f[1][i][0]-f[1][i][1];sort(C+1,C+1+tot);
    for (int i=1;i<=tot;i++) Push(mp(C[i]*C[pos[i]=1],i));
    while (K--) {AMOD(ans,Heap[1].fr%MOD);int ID=Heap[1].sc;Pop();if (pos[ID]<tot) Push(mp(C[ID]*C[++pos[ID]],ID));}
    printf("%d\n",ans);return 0;
}