题解 P3303 【[SDOI2013]淘金】

· · 题解

我的数位DP总结blog

首先写个爆搜,发现对于1\leq i \leq10^{12}的i , f(i) 只有8282 种 . 所以考虑对于这 8282 种数求出有多少数字满足f(i) = 这个数字.

数位dp, 记 dp(x,n,1/0) 表示目前还有n位数字没有决定,除去前导零之后剩下的数字乘积为x ( 所有的x应当事先搜出来放到数组里 ), 目前有/无非零数的方案数.

求出来之后,令a_i为第i个数字被用到的次数,

把a_i从大到小排序,用堆贪心就可以了.

复杂度O(8282 * 12 * 9 * hash()),我自己代码里面用了map,所以比较慢,但是能过就没必要 unordered map 或者 手写Hash 了 .

代码:

#include <bits/stdc++.h>
#define LL long long
#define db double
using namespace std;
template <typename T> void read(T &x){
    x = 0; int f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }
const int S = 8282+5,P = 1e9 + 7;
LL v[S],pw[13]; int cnt; map<LL,int>Id;
namespace INIT{
    map<LL,int>S; int limit;
    inline void dfs(int dep,LL s){
        if (dep>limit){
            if (!S.count(s)){ S[s] = dep; v[++cnt] = s; Id[s] = cnt; }
            else S[s] = min(S[s],dep); 
            return;
        }
        if (S.count(s) && S[s] <= dep) return;
        if (!S.count(s)){ v[++cnt] = s; Id[s] = cnt; }
        S[s] = dep;
        for (int i = 0; i <= 9; ++i) dfs(dep+1,s*i);
    }
    inline void init(){
        int i,j;
        limit = 12,dfs(1,1);
        for (pw[0] = i = 1; i <= 12; ++i) pw[i] = pw[i-1] * 10;
    //  for (i = 1; i <= cnt; ++i) for (j = 0; j <= 9; ++j)
    //      if (Id.count(v[i]*j)) nxt[i][j] = Id[v[i]*j]; else nxt[i][j] = 0;
    }
}
LL dp[S][13][2]; bool vis[S][13][2];
inline LL DP(int s,int n,int tp){
    if (!s || !v[s]) return 0; if (!n) return (tp && v[s] == 1) ? 1 : 0;
    if (vis[s][n][tp]) return dp[s][n][tp]; vis[s][n][tp] = 1;
    LL tot = 0;
    if (tp){
        for (int i = 1; i <= 9; ++i) if (v[s] % i == 0) tot += DP((int)Id[v[s]/i],n-1,1);
    }
    else{
        for (int i = 1; i <= 9; ++i) if (v[s] % i == 0) tot += DP((int)Id[v[s]/i],n-1,1);
        tot += DP(s,n-1,0);
    }
    return dp[s][n][tp] = tot;
}
LL a[S];
inline void work(){
    LL n; register int i,j,k; int x; LL now = 1; bool flag = 0;
    cin >> n; ++n;
    for (i = 12; i >= 0; --i) if ((x=n/pw[i]%10)||flag){
        for (k = 1; k <= cnt; ++k) if (v[k] <= n)
        for (j = 0; j < x; ++j) if (v[k] && v[k] % (now*(j?j:1)) == 0){
            if (flag && !j) continue;
            a[k] += DP(Id[v[k]/now/(j?j:1)],i,(flag||j)?1:0);
        }
        flag = 1,now *= x; if (!now) break;
    }
}
int now[S],n,ans;
struct data{
    int x,y;
    bool operator < (data w) const{ return (db)a[x]*a[y] < (db)a[w.x]*a[w.y]; }
}t;
priority_queue<data>H;
int main(){
    int i,k;
    INIT::init(); work(); n = cnt; cin >> k;
    sort(a+1,a+n+1),reverse(a+1,a+n+1);
    for (i = 1; i <= n; ++i) now[i] = 1,t.x = i,t.y = 1,H.push(t);
    while (k--){
        t = H.top();
        ans = (ans + a[t.x] % P * (a[t.y] % P)) % P;
        H.pop();
        ++now[t.x];
        if (now[t.x] <= n) ++t.y,H.push(t);
    }
    cout << ans << '\n';
    return 0;
}