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

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