Amount of Degrees


题意:给你两个数X,Y(X<=Y<2^31-1),以及k,b,求所有的i∈[X,Y]的数目,i在b进制下只由b个1和若干个0组成。注意有多组数据。

如X=15,Y=20,k=2,b=2,则会有:

17 = 24+20,
18 = 24+21,
20 = 24+22.

所以答案为3


分析:由于X,Y的范围较大,且数据组数较多,所以我们应该考虑有没有复杂度在logn级别的算法。

先来看看朴素算法:我们可以枚举每一个由k个1组成的b进制数,由于X最多有logbX位,每一位可以选择取0或者1,所以我们可以做到O(2logbX)左右的复杂度。但是当b比较小,如2或者3时,这种算法的弊端就显露出来了:我们对于每一位放1还是0都做了很多次判断。

所以我们想到了用动态规划。

先考虑二进制的1情况:如果用f[i][j]表示i位二进制数中出现j个1的数的数量,则f[i][j]=f[i-1][j]+f[i-1][j-1],分别为第i位放0和放1的状态转移。所以我们可以很轻松地预处理出f数组,f数组只需要有32*32个元素即可满足题目的数据要求。接着对于X每一位为1的,ans加上对应的f的值。过程大概是这样的:

比如对于二进制数100110,求小于他的有2个1的数的个数
如果左数第一位为0,则ans+=f[5][2]
如果第一位为1,那么继续讨论1xxxxx
->如果第二位为0(第二位只能为0)那么继续讨论10xxxx
->->如果第三位为0(第三位只能为0)那么继续讨论100xxx
->->->如果第四位为0,由于现在在讨论1000xx,所以xx中只需要有1个x为1,100xx都可以构成与之前讨论得出的答案不同的答案,所以ans+=f[2][1]
->->->如果第四位为1,那么继续讨论1001xx,
->->->->如果第5位为0,那么ans+=f[1][0],
->->->->由于第5不可以为1(为1的话就是10011x,永远无法满足题意),所以直接略过,至此ans为所求。

代码大概是这样的:

由于本人第一次打数位Dp,代码又臭又长,已自裱千遍