Description

小 Z 在玩一个叫做《淘金者》的游戏. 游戏的世界是一个二维坐标. X 轴、Y 轴坐标范围均为 \(1 \dots n\). 初始的时候, 所有的整数坐标点上均有一块金子, 共 $n $块.

一阵风吹过, 金子的位置发生了一些变化. 细心的小 Z 发现, 初始在 \((i, j)\) 坐标处的金子 会变到 \((f(i), f(j))\) 坐标处. 其中 \(f(x)\) 表示 \(x\) 各位数字的乘积, 例如 \(f(99) = 81, f(12) = 2, f(10) = 0\). 如果金子变化后的坐标不在 \(1 \ldots n\) 的范围内, 我们认为这块金子已经被移出游戏. 同时可以发现, 对于变化之后的游戏局面, 某些坐标上的金子数量可能不止一块, 而另外一些坐标上可能已经没有金子. 这次变化之后, 游戏将不会再对金子的位置和数量进行改变, 玩家可以开始进行采集工作.

小 Z 很懒, 打算只进行 \(k\) 次采集. 每次采集可以得到某一个坐标上的所有金子, 采集之后, 该坐标上的金子数变为 0.

现在小 Z 希望知道, 对于变化之后的游戏局面, 在采集次数为 \(k\) 的前提下, 最多可以采集 到多少块金子?

答案可能很大, 小 Z 希望得到对 \(10^9+7\) 取模之后的答案.

Input

共一行, 包含两个正整数 \(n, k\).

Output

一个整数, 表示最多可以采集到的金子数量.

Sample Input

12 5

Sample Output

18

Data Range

对于所有数据, 满足:\(n \leq 10^{12}, k \leq 10^5, k \leq n^2\).

Explanation

由于 \(n\) 不是很大, 在足够小的范围内, 所以我们认为在 \(1 \ldots n\) 这一段范围内 产生的乘积数量比较少, 所以可以先用一个搜索预处理出来所有可能的被采集的坐标.

听说 unique 函数是一个很有用的 STL 加成, 能够把 相邻的 (用错了别怪我没说) 重复元素移出到随机访问容器的最末尾, 并返回最后得到的相邻元素不重复的容器的大小.

针对每一位都进行一个 dp, 然后针对每一个位置把所有对应的 \(dp[]\) 的值加起来, 得到 (单一坐标) 位置存在的金子的数目.

然后用一个堆找出 \(k\) 个最好位置就可以了. 对于较大的 \(k\) 的情况, 我实在是没有什么 做法.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <algorithm>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 400010, maxm = 15;
const lli modr = 1000000007ll;

lli n, K;
int dig[maxm];
lli num[maxn], size[maxn];
lli dp[maxm][maxn][2];

struct state {
    int x, y; lli v;
    state(int x, int y) {
        this->x = x; this->y = y;
        v = size[x] * size[y];
        return ; }
}; bool operator < (state a, state b) {
    return a.v < b.v; }
bool cmp(lli a, lli b) {
    return a > b; }

void dfs(int cur, int depth, lli mult)
{
    if (depth == dig[0]) {
        num[++num[0]] = mult;
    } else {
        if (mult <= 0)
            return ;
        for (int i = cur; i < 10; i++)
            dfs(i, depth + 1, mult * i);
    }
    return ;
}


int main(int argc, char** argv)
{
    scanf("%lld%lld", &n, &K);
    // Filtering individual digits
    while (n > 0) {
        dig[++dig[0]] = n % 10;
        n /= 10;
    }
    // Calculating all possible multiples
    num[++num[0]] = 0;
    dfs(0, 0, 1);
    // Removing duplicates
    sort(num + 1, num + num[0] + 1);
    num[0] = unique(num + 1, num + num[0] + 1) - num - 1;
    // Dynamic programming
    dp[0][2][0] = 1;
    rep(i, 0, dig[0]) rep(j, 1, num[0]) rep(k, 0, 1) if (dp[i][j][k])
        for (int x = (i == 0 ? 0 : 1); x < 10; x++) {
            int tm = lower_bound(num + 1, num + num[0] + 1, num[j] * x) - num;
            dp[i+1][tm][(k+x) > dig[i+1]] += dp[i][j][k];
        }
    rep(i, 1, num[0]) {
        rep(j, 1, dig[0] - 1)
            size[i] += dp[j][i][0] + dp[j][i][1];
        size[i] += dp[dig[0]][i][0];
    }
    size[0] = num[0];
    sort(size + 1, size + size[0] + 1, cmp);
    // Using a heap to choose the best
    lli res = 0;
    priority_queue<state> pq;
    pq.push(state(2, 2));
    while (!pq.empty() && K > 0) {
        state st = pq.top();
        pq.pop();
        res = (res + st.v) % modr;
        if (!(--K)) break;
        if (st.x != st.y) {
            res = (res + st.v) % modr;
            if (!(--K)) break;
            pq.push(state(st.x + 1, st.y));
        }
        if (st.x == 2)
            pq.push(state(st.x, st.y + 1));
    }
    // Output result.
    printf("%lld\n", res);
    return 0;
}