数位DP
一、 度的数量
1、解析
- 题目翻译:满足条件的数x恰好等于k不互不相同的B的整数次幂之和,这等价于x的B进制中恰好有k个1,且只包含1
- 对于给定k和b求解区间[x, y]满足条件的数,相当于求前缀和s后,答案s[y] - s[x - 1]
- 此时这道题目转换成求解小于数字x = $a_{n-1}…a_0(B进制)$的所有满足条件的数
- 此时题目转换成判断x的每一位的可能取值,唯一限制即1的个数,假设为cnt
- 假设当前枚举到t这一位,还剩下n位
- 如果t=0,则这意味仍有k - cnt个1可以选择,此时方案数为c[n][k - cnt]
- 如果t=1,则同上,此时方案数为c[n][k - cnt - 1]
- 如果此时t > 1,则说明这个数字不可能由k个1组成,舍弃
- 假设当前枚举到t这一位,还剩下n位