ural 1057. Amount of Degrees (b进制数位dp)

题目链接
题意:设条件A为一个数恰好是k个互不相同的b的整数次幂的和,问某一个区间内满足条件A的数的个数是有多少个。

Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2:
17 = 24+20,
18 = 24+21,
20 = 24+22.

思路:数位dp..需要理解清楚恰好有k个b的互不相同的整数次幂的和这句话。

如果恰好是b的整数幂。。可以转化成b进制。。

互不相同。。说明。。所有位置上的数字要么是0,要么是1.

于是题目可以转化成求某区间内,满足一个数的b进制中恰好有k个1,其余都是0的数的个数有多少个。

然后就是数位dp的套路了。。。

注意dp数组的大小。。。应该按照位数最多的2进制考虑。。。一开始是按照10进制考虑结果只开了dp[15][15]….简直蠢哭。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz