题解 SP8177 【JZPEXT - Beautiful numbers EXTREME】
s_r_f
2020-04-28 22:43:19
[我的数位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)
首先不难设出状态$:$ $dp(s,r,n)$ 表示目前已经确定下来的前缀$mod$ $2520$ 为 $r,$ 目前的 $1..9$ 是否存在状压到 $s$ 里 $,$ 还有 $n$ 位没有确定$.$
但如果直接设状态状态总数为 $2\times10^7,$再乘上每次转移是 $O(10)$
显然会 $T$ 飞
由于我们只需要考虑集合里面数的$lcm$大小$,$所以有些状态是可以合并的$,$就写个预处理把它合并一下就好了$.$
$P.S:$ 我代码里面没有合并干净$,$是$73$种状态$,$
如果真正合并干净了那就是$48$种状态$.$
$DP$部分代码$:$
$($ 这个代码是在$codeforces$上一道同样范围的题中通过的$,$但不保证此处一定能通过 $)$
```cpp
LL pw[19];
int trans[1<<9],tid[1<<9]; bool used[1<<9];
int cnt,v[73+5],nxt[73+5][10];
inline void init(){
int i,j,k,id,l = 1<<9,s;
for (pw[0] = i = 1; i <= 18; ++i) pw[i] = pw[i-1] * 10;
for (i = 0; i < l; ++i){
trans[i] = i;
for (j = 9; j >= 1; --j) if (trans[i] >> (j-1) & 1)
for (k = j + j; k <= 9; k += j) if (trans[i] >> (k-1) & 1){
trans[i] &= ((1<<9)-1)^(1<<(j-1)); break;
}
used[trans[i]] = 1;
}
for (i = 0; i < l; ++i) if (used[i]) ++cnt,v[cnt] = i,tid[i] = cnt;//cnt==73
for (i = 0; i < l; ++i) if (id = tid[i]){
for (v[id] = 1,j = 1; j <= 9; ++j) if (i>>(j-1)&1) v[id] = lcm(v[id],j);
for (nxt[id][0] = id,j = 1; j <= 9; ++j) nxt[id][j] = tid[trans[i|(1<<j-1)]];
}
}
inline bool check(int id,int r){ return r % v[id] == 0; }
LL dp[74][2520][20]; bool vis[74][2520][20];
inline LL DP(int s,int r,int n){
if (!n) return check(s,r) ? 1 : 0;
if (vis[s][r][n]) return dp[s][r][n]; vis[s][r][n] = 1;
LL tot = 0;
for (int i = 0; i <= 9; ++i) tot += DP(nxt[s][i],(r*10+i)%2520,n-1);
return dp[s][r][n] = tot;
}
```