比较有趣(有难度)的数位 。

分析

我们考虑 表示 每一位的积。那么我们先考虑一维的情况，那么我们要求出 最多的一个 。那么这个考虑数位 解决。但是我们发现 还是比较大的。直接表示状态是表示不出来的。但是 就有了一个非常好的性质。 。这样我们发现其实有用的状态非常少，大概 个左右。那么直接用 表示考虑第 位，积 时，没有前导零，是否顶住极限的方案数。这样我们就解答了一维的答案。但是我们是要求前 大的 的答案。这个就是一个套路了，将 排序。那么最优的答案就可以用一个堆维护。

• 关于堆维护，一：把 拓展到 。二：把 拓展到 和 。本代码选择前者。

  代码

  #include<bits/stdc++.h>
  using namespace std;
  #define ll long long
  const ll N = 4e5 + 100,mod = 1e9 + 7;
  ll de[10][4] = {
   /*2,3,5,7*/
    {0,0,0,0}, // 0
    {0,0,0,0}, // 1
    {1,0,0,0}, // 2
    {0,1,0,0}, // 3
    {2,0,0,0}, // 4
    {0,0,1,0}, // 5
    {1,1,0,0}, // 6
    {0,0,0,1}, // 7
    {3,0,0,0}, // 8
    {0,2,0,0}, // 9
  };
  ll h[N],top,n,K,p[20],ans[N],tot;
  map<ll,bool> mp;
  ll f[15][46][29][21][18][2];
  void Init(ll x) {
    if(mp[x]) return;if(x > n) return;
    mp[x] = 1;ll d[4] = {2,3,5,7};
    h[++top] = x;
    for(int i = 0;i < 4;i++) Init(x * d[i]);
  }
  ll dp(ll now,ll _2,ll _3,ll _5,ll _7,ll st,ll limit) {
    if(_2 < 0 || _3 < 0 || _5 < 0 || _7 < 0) return 0;
  //    cout << _2 << " " << _3 << " " <<_5<<" "<< _7 << " qian dao " << st <<" limit:: "<<limit<< endl;
    if(now < 0) return !_2 && !_3 && !_5 && !_7 && !st;
    if(f[now][_2][_3][_5][_7][limit] != -1 && !st) return f[now][_2][_3][_5][_7][limit];
    ll res = 0,lim = limit ? p[now] : 9;
    for(ll i = !st;i <= lim;i++) {
  //        cout <<"xuanqu "<< i << endl;
        res += dp(now-1,_2-de[i][0],_3-de[i][1],_5-de[i][2],_7-de[i][3],st&&(!i),limit&&(i==p[now]));        
    }
    if(!st) f[now][_2][_3][_5][_7][limit] = res;
    return res;
  }
  ll solve(ll x) {
    ll _2 = 0,_3 = 0,_5 = 0,_7 = 0,y = 0;
    y = x;while(!(y % 2)) y /= 2,_2++;
    y = x;while(!(y % 3)) y /= 3,_3++;
    y = x;while(!(y % 5)) y /= 5,_5++;
    y = x;while(!(y % 7)) y /= 7,_7++;
  //    cout << p[0] << endl;
    return dp(tot,_2,_3,_5,_7,1,1);
  }
  struct Node {
    ll x,y;
    bool operator <(const Node a) const {
        return ans[x] * ans[y] < ans[a.x] * ans[a.y];
    }
  };
  priority_queue<Node> heap;
  int main() {
    scanf("%lld%lld",&n,&K);
    ll tmp = n;
    while(tmp) p[tot++] = tmp % 10, tmp /= 10;tot--;
    Init(1);memset(f,-1,sizeof(f));
    for(ll i = 1;i <= top;i++) {ans[i] = solve(h[i]);/*cout << "i:: "<< i << "  " << ans[i] << endl;*/}
    sort(ans + 1,ans + 1 + top);
    for(ll i = 1;i <= top;i++) heap.push((Node) {i,top});
    ll Ans = 0;K = min(K,top * top);
    while(K--) {
        ll x = heap.top().x,y = heap.top().y;heap.pop();
        Ans = (Ans + ((ans[x] % mod) * (ans[y] % mod)) % mod) % mod;
        if(y != 1) heap.push((Node) {x,y - 1});
    }
    printf("%lld\n",Ans);
    return 0;
  }