设 \(c(x)\) 为满足 \(f(i) = x\) 即各位数字之积 \(=x\) 的 \(i\) 的个数。
那么变化之后格子 \((x,y)\) 上有的金块个数就是 \(c(x) \cdot c(y)\)。
容易发现 \(c(x)\) 中的 \(x\) 分解后若除了 \(2,3,5,7\) 还有其他质因子，\(c(x) = 0\)。
问题就在于 \(c(x)\) 的求法，我们可以用数位 DP（个人喜欢记搜），状态需要记录搜到第 \(x\) 位，组成的数 \(= 2^a \cdot 3^b \cdot 5^c \cdot 7^d\) 中的指数 \(a,b,c,d\)。
然后用一个常量数组记录一下 \(1 - 9\) 分解之后的四个指数，搜索的时候注意除了前导 \(0\) 的时候都不能选 \(0\)，以及所有位都是 \(0\) 时最后一位会算作前导 \(0\) 需要特判。
于是我们 DFS 一遍 \(n\) 以内的质因子只有 \(2,3,5,7\) 的数（或者直接枚举四个指数就行），求出其对应的 \(c\) 函数值，然后把所有的 \(c\) 函数值从大到小排个序。
然后我们设 \(c\) 函数值有 \(cnt\) 个，往大根堆里面丢 \(cnt\) 个形如 \((x,1)\) 的二元组，大根堆的优先级是二元组两个数的 \(c\) 值之积。
从大根堆取出一个二元组，计算对答案的贡献，再把第二个数加一丢回去。这样执行 \(k\) 次就行了。
注意实现细节。
以及，不要问为什么我用 pbds 的优先队列。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
using namespace std;
const int LEN = 12;
const int divi[10][4] = {
{0,0,0,0},
{0,0,0,0},
{1,0,0,0},
{0,1,0,0},
{2,0,0,0},
{0,0,1,0},
{1,1,0,0},
{0,0,0,1},
{3,0,0,0},
{0,2,0,0}
};
const long long N = 1e12;
const int CNT = 2e4;
const long long mod = 1e9 + 7;
long long n;
int k;
int tot,d[LEN + 5];
long long f[LEN + 5][LEN * 3 + 5][LEN * 2 + 5][LEN + 5][LEN + 5][2];
long long h[CNT + 5],c[CNT + 5];
int cnt;
void dfs(int x,long long prod)
{
static const long long d[4] = {2,3,5,7};
if(prod > n)
return ;
h[++cnt] = prod;
for(register int i = x;i < 4;++i)
dfs(i,prod * d[i]);
}
long long dfs(int x,int _2,int _3,int _5,int _7,int lead,int top)
{
if(_2 < 0 || _3 < 0 || _5 < 0 || _7 < 0)
return 0;
if(!x)
return !_2 && !_3 && !_5 && !_7;
if(!top && ~f[x][_2][_3][_5][_7][lead])
return f[x][_2][_3][_5][_7][lead];
long long ret = 0;
int bound = top ? d[x] : 9;
for(register int i = x > 1 ? 0 : 1;i <= bound;++i)
{
if(!lead && !i)
continue;
ret += dfs(x - 1,_2 - divi[i][0],_3 - divi[i][1],_5 - divi[i][2],_7 - divi[i][3],lead && !i,top && i == bound);
}
if(!top)
f[x][_2][_3][_5][_7][lead] = ret;
return ret;
}
long long solve(long long x)
{
int _2 = 0;
while(!(x % 2))
x /= 2,++_2;
int _3 = 0;
while(!(x % 3))
x /= 3,++_3;
int _5 = 0;
while(!(x % 5))
x /= 5,++_5;
int _7 = 0;
while(!(x % 7))
x /= 7,++_7;
return dfs(tot,_2,_3,_5,_7,1,1);
}
struct note
{
int x,y;
inline bool operator<(const note &a) const
{
return c[x] * c[y] < c[a.x] * c[a.y];
}
};
__gnu_pbds::priority_queue<note> pq;
long long ans;
int main()
{
memset(f,-1,sizeof f);
scanf("%lld%d",&n,&k);
dfs(0,1);
long long temp = n;
while(temp)
{
d[++tot] = temp % 10;
temp /= 10;
}
for(register int i = 1;i <= cnt;++i)
c[i] = solve(h[i]);
sort(c + 1,c + cnt + 1,greater<long long>());
k = min(k,cnt * cnt);
for(register int i = 1;i <= cnt;++i)
pq.push((note){i,1});
for(register int i = 1;i <= k;++i)
{
note cur = pq.top();
pq.pop();
ans = (ans + c[cur.x] * c[cur.y]) % mod;
if(cur.y == cnt)
continue;
pq.push((note){cur.x,cur.y + 1});
}
printf("%lld\n",ans);
}