Codeforces 55D Beautiful numbers

Posted by

题目链接

http://codeforces.com/problemset/problem/55/D

题意

求一段区间\([l,r]\)之间beautiful number的数目。

我们称一个数为beautiful number,当它能被它的每一个非零位整除。

题解

数位DP:设\(f[dep][stat][sum]\)表示还有\(dep\)位没有填,\(stat\)用二进制记录已经填了哪些数,填出来的数为\(sum\)。

由于\(1\),\(0\)不需要考虑,\(stat\)维开\(2^8\)即可;如果一个数能整除\(2 \sim 9\)中所有的数,那么一定是这\(8\)个数最大公倍数的倍数,即\(sum\)维可以对\(2520\)求余。

dfs枚举每一位填哪个数即可。

状态转移方程:

假设这这一位填数\(i\):

\[ f[dep][stat][sum]=\begin{cases}
\sum_{i=0}^1 {f[dep-1][stat][(sum\times 10+i)mod\ 2520]}\\
\sum_{i=2}^9 {f[dep-1][stat\ or\ 2^{i-2})][(sum\times 10+i)mod\ 2520]}
\end{cases} \]

边界条件:

当\(dep=0\)的时候统计贡献,所有位都能整除时返回\(1\)。

注意:dfs的时候还要多记录一个\(flag\)表示有没有触碰到边界,碰触到边界的时候不可以调用\(f\)也不可以更新\(f\)

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注