1. 首页
  2. 数位DP

CodeForces 55D Beautiful numbers (数位DP)

居然可以这样处理orz~~~

下面为转载内容:

a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits.
问一个区间内[l,r]有多少个Beautiful数字
范围9*10^18

数位统计问题,构造状态也挺难的,我想不出,我的思维局限在用递推去初始化状态,而这里的状态定义也比较难
跟pre的具体数字有关

问了NotOnlySuccess的,豁然开朗  Orz

一个数字要被它的所有非零位整除,即被他们的LCM整除,可以存已有数字的Mask,但更好的方法是存它们的LCM{digit[i]}
int MOD = LCM{1,2,9} = 5 * 7 * 8 * 9 = 2520
按照定义,数字x为Beautiful :
x % LCM{digit[xi]} = 0
即 x % MOD % LCM{digit[xi]} = 0
所以可以只需存x % MOD,范围缩小了
而在逐位统计时,假设到了pre***(pre指前面的一段已知的数字,而*是任意变)
( preSum * 10^pos + next )  % MOD % LCM(preLcm , nextLcm)
=  ( preSum * 10 ^ pos % MOD + next % MOD ) % LCM(preLcm , nextLcm)
== 0
而next,nextLcm是变量,上面的比较式的意义就是
在已知pos , preSum , preLcm情况下有多少种(next,nextLcm)满足式子为0
而这个就是一个重复子问题所在的地方了,需要记录下来,用记忆化搜索
dfs(pos , preSum , preLcm , doing)
加一个标记为doing表示目前是在计算给定数字的上限,还是没有上限,即***类型的
这样就将初始化以及逐位统计写在一个dfs了,好神奇!!!

还有一点,10以内的数字情况为2^3 , 3^2 , 5 , 7
所以最小公倍数组合的情况只有4*3*2*2 = 48
可以存起来,我看NotOnlySuccess的写法是
for(int i = 1 ; i <= MOD ; i ++)
{
if(MOD % i == 0)
index[i] = num++;
}
很棒!!

所以复杂度大概为19*2520*48*10(状态数*决策数)

我觉得这题状态的设计不能跟具体数字分开,否则会很难设计吧
所以用记忆化搜索,存起来
用具体数字去计算,重复的子问题跟pre关系比较密切
有一个比较重要的切入点就是LCM,还有%MOD缩小范围,才能存储

还有优化到只需%252的,更快
不过我觉得%2520比较好理解

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/352 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

发表评论

gravatar

快来吐槽一下吧!

  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40