题目链接：戳我
昨天做的题了，今天补一发题解。
是一个比较奇怪的数位DP。详细的我还是写代码注释里好了，感觉直接说不好描述。
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#define MAXN 200010
#define mod 1000000007
using namespace std;
int tot,cnt,len,nn;
int a[15],num[MAXN];
long long N,K,x,ans;
long long b[MAXN*10],dp[15][MAXN][2],siz[MAXN];
struct Node
{
int x,y;
long long val;
friend bool operator < (struct Node x,struct Node y)
{return x.val<y.val;}
Node(int u,int v)
{
x=u,y=v;
val=1ll*siz[num[u]]*siz[num[v]];
}
//构造函数
};
priority_queue<Node>q;
inline void dfs(int now,int x,long long kk)
{
if(kk==0) return;
if(x>len){b[++cnt]=kk;return;}
for(int i=now;i<=9;i++) dfs(i,x+1,kk*i);
}
//首先通过dfs求出来合法的（也就是会被转移到的格子）
//为什么这样时间复杂度是正确的？大家计算一下，对于该题目里的格子，它转移到的格子的数分解下来
//也不过就是(2^a)*(3^b)*(5^c)*(7^d)
//所以总的状态数量大概就在1e5的级别
inline bool cmp(const int x,const int y){return siz[x]>siz[y];}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%lld%lld",&N,&K);
while(N){a[++len]=N%10;N/=10;}//按位分解
dfs(0,0,1);
sort(&b[1],&b[1+cnt]);
cnt=unique(&b[1],&b[1+cnt])-b-1;
//离散化预处理
dp[0][2][0]=1;
//dp[i][j][0/1]表示的是现在处理到了第i位，数位乘积为j，0表示它当前位小于等于n对应的位上的数
//1表示大于
for(int i=0;i<=len;i++)
{
for(int j=1;j<=cnt;j++)
{
for(int k=0;k<=1;k++)
{
if(!dp[i][j][k]) continue;
for(int p=1;p<=9;p++)
(dp[i+1][lower_bound(&b[1],&b[1+cnt],b[j]*p)-b][k+p>a[i+1]]+=dp[i][j][k])%=mod;
}
}
}
//注：我们将i+1当做当前位，i当做上一位，以下叙述均按此
//注意乘积比较大，所以要离散化，而这里使用lower_bound来确定位次就是一个不错的选择
//当前位填p,进行转移（感觉转移方程式还是很好懂的吧qwqwq，思考一下就行了）
//至于第三维为什么写k+p>a[i+1]呢？
//当上一位小于等于的时候，k=0，只有当前位>a[i+1]的时候，它才会比原数N大（对吧qwq）
//当上一位大于的时候，只要当前位等于，它就会比原数N大，更别说大于了qwqwq
//（懵懵懂懂
for(int j=1;j<=cnt;j++)
{
num[j]=j;
for(int i=1;i<len;i++)siz[j]+=dp[i][j][1]+dp[i][j][0];
siz[j]+=dp[len][j][0];
}
sort(&num[2],&num[cnt+1],cmp);
q.push(Node(2,2));//为什么从2,2开始？因为这里是第一个
//取前K大，用优先队列维护即可
while(!q.empty())
{
int u_x=q.top().x,u_y=q.top().y;
long long u_val=q.top().val;
q.pop();
ans=(ans+u_val)%mod;
nn++;
if(nn==K) break;
if(u_x!=u_y)
{
ans=(ans+u_val)%mod;
//如果x坐标y坐标不一样要加两遍（也就是乘2的意思），至于为什么，大家想想吧qwq
q.push(Node(u_x+1,u_y));
nn++;
if(nn==K) break;
}
if(u_x==2) q.push(Node(u_x,u_y+1));
}
printf("%lld\n",ans);
return 0;
}
//完结撒花~
备注：该代码很大程度上参考了网上的题解（因为本弱菜实在是写不出来正解。。。要是考试估计也是打个暴力走人了），但是网上题解写的实在不是很详细，所以这里特地来补一篇详细的，希望大家都能看懂qwq