CF55D-Beautiful numbers （数位dp）

$lcm(1,2,3,4,5,6,7,8,9)=2520$

• 若 $x$ 能被它自己的所有非零位的数字整除，即能被它们的最小公倍数整除， x ≡ 0 ( m o d   l c m ( { d i g i t [ i ] } ) ) x \equiv 0(mod\ lcm(\{digit[i]\})) x≡0(mod lcm({digit[i]}));
• 2520 ≡ 0 ( m o d   l c m ( { d i g i t [ i ] } ) ) 2520 \equiv 0(mod\ lcm(\{digit[i]\})) 2520≡0(mod lcm({digit[i]}))
• 若 x ≡ 0 ( m o d   l c m ( { d i g i t [ i ] } ) ) x \equiv 0(mod\ lcm(\{digit[i]\})) x≡0(mod lcm({digit[i]}))，则 ( x   m o d   2520 ) ≡ 0 ( m o d   l c m ( { d i g i t [ i ] } ) ) (x\ mod\ 2520) \equiv 0(mod\ lcm(\{digit[i]\})) (x mod 2520)≡0(mod lcm({digit[i]}))

由以上可得，判断 $x$ 只需判断 $xmod2520$。

• 令 dp[i][j][k] 表示前 $i$ 位，表示的数模 $2520$ 的余数为 $j$，前 $i$ 位的最小公倍数为 $k$，这样空间为 $dp[20][2525][2525]$，明显 $MLE$；
• 考虑到 $2520$ 的约数共 $48$ 个，不是约数的最小公倍数都没有用，所以，可以将换为 $k$ 前 $i$ 位最小公倍数的元素个数，最后一维通过离散化降到 $50$，从而空间为 $dp[20][2525][50]$。