hdu 3967 Zero’s Number (不允许前导0(新写法)的数位dp)

题目链接

题意:给出l,r,k,定义f(n,k)为将数n分成左右两个非空的部分,再求和之后能被k整除的方案数。

现在问区间[l,r]中所有f(i,k)的和。

思路:数位dp…

枚举一下分点即可。。想到这个这题就A了。。。

然后相当于做分点个数个数位dp…求和即可。

dp[i][j][k][p]表示第i位,前半部分%k的结果,后半部分%k的结果,是否有前导0.

然后关于前导0这个。。。换了一种写法。。。加了一个状态在dp数组里。。。

不然每次都要一个if。。。感觉有点丑。。。。这样写简介了一点。。。

以及。。因为每次k是不同的。。。我dp状态记录的时候又没有记录k…所以记得每次初始化成-1。。。

因为忘记这个结果第二个样例调了好久一直是31。。。。

 

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz