题解 P3303 【[SDOI2013]淘金】
s_r_f
2020-04-30 22:02:57
[我的数位$DP$总结$blog$](https://www.luogu.com.cn/blog/s-r-f/oi-bi-ji-shuo-wei-dp-ge-ji-dui-shuo-wei-dp-di-yi-dian-li-xie)
首先写个爆搜$,$发现对于$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$ 了 $.$
代码$:$
```cpp
#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;
}
```