hdu 4507 吉哥系列故事——恨7不成妻 (返回平方和的数位dp)

题目链接
题意:如果一个整数符合下面3个条件之一,那么我们就说这个整数和7有关——
1、整数中某一位是7;
2、整数的每一位加起来的和是7的整数倍;
3、这个整数是7的整数倍;

现在问题来了:吉哥想知道在一定区间内和7无关的数字的平方和。

思路;如果是求count的话毫无难度。。。和之前的题目没什么区别。。不多说了。

但是是求平方数。。。一开始我的做法是在dfs中加一个LL 的参数表示当前的和,然后每次到dfs的出口,之前统计count的时候返回的是1,表示找到了满足条件的一个数,那这回就返回平方和。。但是这样做是错的。。。具体为什么错没有想得很明白。。。大概会少算?

然后参考了如下博客:
hdu4507解题报告1
hdu4507解题报告2

适牛的博客之数位dp

 

正解是,之前的dp只统计了一个cnt,这回要同时统计cnt,sum,sqsum(平方和)..

 

我们先讨论如何求得满足条件的数的和。

 

我们设某次进入dfs的数是x,当前长度为pos(长度是越来越短的,因为是从高位到低位,对于没有处理到的低位,是按0算的,比如一个五位数xxxxx,第一次dfs以后也许得到4xxxx,x表示没有填的数的位置,实际上这个数就是40000),当前位置要防止的数字是i,考虑其位置,i对这个数的大小(不是和,就是最后要得到的一个数)的贡献是i*10^(pos-1),设为f. 那么当前的数就是f+x. 我们要求的就是所有f+x的和。现在我们考虑当新添加pos位的数字i对于和的贡献。

当新添加i时,相当与把之前的数整体左移了一位,相当于×10(因为之前[1,x]中的每个满足条件的数都乘了10,所以和也乘了10),然后对于新添加的i,它的贡献是i*cnt[x],含义是对于之前[1,x]所有满足条件的每个数,都进行了pos位置填i的操作,所有对于所有满足条件的和一共添加了cnt[x]个i.

如果写成用递推的式子就是  

sum[10*x+i] = 10 * sum[x] + cnt[x]*i;//感谢@clq学长

如果用dfs的话式子就是

sum[new_state] = Σ{ sum[old_state] + (number to add at the postion) * (its base) * count[old_state] }。

 

接下来我们考虑维护平方和,方法类似。

(f+x)^2=f*f+x*x+2*f*x.

f*f直接可以算,x*x..其实就是上一层dfs得到的(f’+x’)^2嘛…也就是sum2[x] (sum2表示平方和)

2*f*x也可以算,x就是上一个状态的和。

同样,我们考虑现在已经有了x,处理到pos位置,填到该位置的数字是i的时候对平方和的影响。

x*x部分在上一个状态处理过了,即为sum2[x], 2*f*x 也可以通过sum[x]得到…

注意f*f,同样,对于之前的[1,x]中每个满足的数,都相当于第pos位添加了i,每个数对平方和的贡献都是i*i,所以要*cnt[x]… 

 

以及要不断取模,为了方便写了两个函数来搞,代码看起来清楚一些。。。

哦,还有一个小坑。。取模相减以后可能为负数。。。。记得加MOD…

 

 

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz