思路
这是一道数位dp问题，对于数位dp问题关键就在于分类讨论。
首先我们把数字 n 对于B进制来进行分解 ，将每一位上的数字存入一个数组中，然后从高位往低位去讨论，
首先 对于第 i 位数字 x 有三种情况
- x = 0 ：则 i 位上只能取 0 ，所以直接讨论 i-1 位就可以了
- x = 1 ：则 i 位上取 0 的时候，后面i-1位都可以随意取值 ，取 1 的时候，后面i- 1位要再小于题目的数的前提下取值，并且能取 k-last-1 个 1 ，
- x > 1 ：则 i 位上 可以取 1 ，0 ，并且后面 i-1 位可以随便取。
这里 i-1位随便取 和 对于i-1 位讨论的区别，就体现在前一个直接用组合数 f[i-1][k-last]就可以，后面则需要再进入循环去讨论。
最后对于最后一位进行单独讨论，如果对于 最后一位时 ，所有的k个1都已经取好了，也就是k==last了，才做res++。
代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 35;
int K, B;
int f[N][N];
void init(){//求组合数
for(int i=0;i<=N;i++){
for(int j=0;j<=i;j++){
if(!j)f[i][j]=1;
else f[i][j]=f[i-1][j-1]+f[i-1][j];
}
}
}
int dp(int n){
if (!n) return 0;//如果n==0，那么就直接放回0
vector<int> v;
while (n) v.push_back(n % B), n /= B;
int res=0;
int last=0;//表示已经取了多少个1
for(int i=v.size()-1;i>=0;i--){//从最高位对每一位数讨论
int x=v[i];
if(x){
res += f[i][K - last];//加上第i位取0的时候的组合数，也就是对于后面i位取k-last个1的数量
if (x > 1)//如果x>1，就可以直接用组合数表示出来，不用进行讨论，也就是i位取1的时候，后面i位随便取k-last-1个1
{
if (K - last - 1 >= 0) res += f[i][K - last - 1];
break;
}
else//如果x==1，那么i位取1的时候，还要进行讨论，后面i位不能随便取，也就不是组合数
{
last ++ ;
if (last > K) break;
}
}
if (!i && last == K) res ++ ;// 对于最后一位来特殊来考虑
}
return res;
}
int main()
{
init();
int l, r;
cin >> l >> r >> K >> B;
cout << dp(r) - dp(l - 1) << endl;
return 0;
}
看了一个小时终于看明白了
牛逼我会了
看了很多题解，还是你的最清晰
为什么时1的个数加起来是k 而不是其他数
题目是 恰好等于 K 个互不相等的 B 的整数次幂之和 ，所以幂次上只能是 1
x > 1 ：则 i 位上 可以取 1 ，0 ，并且后面 i-1 位可以随便取。
/// 第 i 位能取2.3.4.。。。。吗（如果是十进制的话）
应该是取2,3,4…就不满足题意了，只可能取 B ^ i 或不取，即对应1, 0
作者写得不错，我也研究了一下，写了更详细的代码。有需要的大佬可以移步
https://www.acwing.com/solution/content/34003/
希望对大家有帮助。
17的三进制是110，是我理解错了呢，还是博主写错了啊
一个bug 你先输入数据再初始化就不对！
必须先初始化再 输入数据
我也是 debug了好久 大佬知道为什么吗
不知道哎。呜呜呜呜呜
关于这个问题，以下仅是我的一点个人猜想，如有错误请大佬指正。
如果先输入数据再初始化发生了错误，很可能是在定义全局变量的时候写成了下面的格式：
由于f数组和K、B两个变量靠的很近，f数组是有可能将K、B两个变量改写的。
如果使用
的方式去查看对应变量地址的话，可能会出现f[N - 1][N - 1]的地址超过了K和B，所以在初始化的时候会导致K和B的数值被改写，而不是原来输入的数值了。
可以考虑用以下方式去定义变量：
1、将全局数组声明在各种变量的后面，防止数组的地址超过其他全局变量；
2、对于本题，可以考虑定义成以下形式：
数组多开一些冗余空间，然后在init的时候仍然是使用N，这样应该可以避免变量被改写。
’‘’
for (int i = 0; i <= N; i ++)
‘’‘
数组越界了，N个元素的数组，下标最多到N - 1。
是的，数组越界了，代码有小问题，改了之后随便放
我再来小小总结一下吧， 也是我自己刚看懂的；
1；当前位为 大于1时：
这位可以取0， 那么就是剩下位中取k-last个1；
这位可以取1， 那么就是剩下位中取k-last-1个1；(但必须大于1的时候才可以取）
2：当这位是1时， 那么代表着一种确定的 B^i ,所以不能动， 但仍可以枚举这位是0的情况；
3：当这位是0时， 这位只能取0， 那么只能看下一位的， 那么就归结到下一位的分类中了， 所以不用讨论；
哇，想半天没搞懂，看了大佬的题解豁然开朗，您太强了~~~
你这个求组合数的时候 i=0 i-1=-1不会越界么
哦哦我弄错了sorry
有点细节没想通，看你注释瞬间懂了，靠谱！
哈哈，多谢支持(ง •_•)ง
刚发现的bug，init里面i不能等于N虽然你代码能a但是如果把int k,b放到int f下面就不a了
我也发现了
大赞！！！
感谢支持！！(●’◡’●)
你好，请问第i位的值x对第i位取0或1是怎么产生影响的?
这里有两个分枝，左边的分支是对于第i位取0~x-1，这种分支用组合数就可以表示，但是如果x=0，那么这个分支就不存在，就继续做右边的分支，如果x=1，那么组合数中第i位取1的情况就没有了，然后做右边的分支，如果x>1，那么组合数是完整的，但是由于题目每一位只能取0或者1，那么对于右边的分支，也就是第i位取x的时候，是不能取x的（因为x不是0/1），所以就到此break了，不懂的话建议仔细看下y总的视频o(￣▽￣)ブ
嗯嗯，好嘞，非常感谢。
不客气，一起加油(ง •_•)ง
左边的分支是对于第i位取0~x-1，，这句话不太理解，不是只能去0或者1吗，怎么会取到x-1去
佬，我想问下，x>1,右边是为啥break了…我困惑于代码里面没有直接枚举第i位到底取什么啊