1. 首页
  2. 数位DP

HDU 4507 恨7不成妻 (数位DP)

题目大意:求指定范围内与7不沾边的所有数的平方和。通常的数位dp只是用来统计条件个数的,由于是求条件数的平方和,所以需要在过程中维护平方和。

解题思路:(以下内容来自互联网)

与7不沾边的数需要满足三个条件。

①不出现7

②各位数和不是7的倍数

③这个数不是7的倍数

这三个条件都是基础的数位DP。

但是这题要统计的不是符合条件个数,而是平方和。

也就是说在DP时候,要重建每个数,算出平方,然后求和。

需要维护三个值(推荐使用结构体), 假定dfs推出返回的结构体是next,当前结果的结构体是ans

①符合条件数的个数 cnt

②符合条件数的和 sum

③符合添加数的平方和 sqsum

其中①是基础数位DP。②next.sum+(10^len*i)*ans.cnt,其中(10^len*i)*ans.cnt代表以len为首位的这部分数字和。

③首先重建一下这个数,(10^len*i+x),其中x是这个数的后面部分,则平方和就是(10^len*i)^2+x^2+2*10^len*i*x,其中x^2=next.sqsum

整体还要乘以next.cnt,毕竟不止一个。

这样sqsum+=next.sqsum

sqsum+=(2*10^len*i*x)*next.cnt=(2*10^len*i)*next.sum(神奇的化简)

sqsum+=(10^len*i)^2*next.cnt

 

然后就是本题鬼畜的地方了,cnt,sum,sqsum,三个都是达到了int64极限。

也即是说凡是这三个值参与运算的地方,都要狠狠打上mod,尤其是cnt!一坨坨mod出现了。

 

mod之后统计函数也有个小陷阱,那就是f(r)在mod之后有可能小于f(l-1)。也就是要对负数取正数模。

负数取模的方法(ans%mod+mod)%mod。

 

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

发表评论

gravatar

快来吐槽一下吧!

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