【题目来源】
【题目描述】
求给定区间 [X,Y] 中满足下列条件的整数个数：这个数恰好等于 K 个互不相等的 B 的整数次幂之和。例如，设 X=15，Y=20，K=2，B=2，则有且仅有下列三个数满足题意：
17=2^4+2^0
18=2^4+2^1
20=2^4+2^2
【输入格式】
第一行包含两个整数 X 和 Y，接下来两行包含整数 K 和 B。
【输出格式】
只包含一个整数，表示满足条件的数的个数。
【输入样例】
15 20
2
2
【输出样例】
3
【数据范围】
对于全部数据，1≤X≤Y≤2^31-1，1≤K≤20，2≤B≤10。
【算法分析】
● 本题与“AcWing 1081：度的数量”（）的代码完全一致。详见：
● 核心思路与预处理
（一）问题转换
题目要求统计的数字，其 b 进制表示中的每一位只能是 0 或 1，并且 1 的总数恰好为 k。这本质上是在 b 进制下，寻找所有二进制表示（但用 b 进制书写）中 1 的个数为 k 的数。
（二）组合数预处理
void init() {for(int i=0; i<N; i++)for(int j=0; j<=i; j++)if(j==0) f[i][j]=1;else f[i][j]=f[i-1][j-1]+f[i-1][j];
}
f[i][j] 表示从 i 个位置中选出 j 个位置放置 1 的组合数，即 C(i, j)。
使用帕斯卡公式（杨辉三角）递推计算：C(i, j)=C(i-1, j-1)+C(i-1, j)。
这个组合数数组是后续计算的核心工具。
● 核心计算函数 dp(int n)
（一）数位分解
vector<int> v;
while(n) {v.push_back(n%b);n/=b;
}将数字 n 转换为 b 进制表示，v[0] 存储最低位，v[v.size()-1] 存储最高位。
（二）逐位统计逻辑
int cnt=0,pre=0;
for(int i=v.size()-1; i>=0; i--) {int x=v[i];if(x>0) {cnt+=f[i][k-pre];if(x>1) {if(k-pre-1>=0) cnt+=f[i][k-pre-1];break;} else {pre++;if(pre>k) break;}}if(i==0 && pre==k) cnt++;
}变量说明：
cnt：累计满足条件的数字个数。
pre：已经确定的 1 的个数（在前面的高位中）。
i：当前处理位的位置索引（从最高位向最低位）。
x：当前位的值（在 b 进制下）。
处理逻辑详解：
(1) 当前位 x>0 的情况
cnt+=f[i][k-pre];如果当前位取 0：那么剩余的 i 个低位中，需要放置 k-pre 个 1。
这种情况的数量是 C(i, k−pre)。
(2) 当前位 x>1 的情况
if(x>1) {if(k-pre-1>=0) cnt+=f[i][k-pre-1];break;
}如果当前位可以取 1：那么剩余的 i 个低位中，需要放置 k-pre-1 个 1。
这种情况的数量是 C(i, k−pre-1)。
break 的原因：由于 x>1，当前位如果取 1，已经小于原数的这一位，所以后续低位可以任意选择（只要满足总 1 数条件）。统计完这种情况后，不需要再考虑固定当前位等于 x 的情况，因为原数本身不可能满足条件（有非 0 非 1 的位）。
(3) 当前位 x==1 的情况
else {pre++;if(pre>k) break;
}当前位必须取 1（因为原数这一位就是 1，且不能取 0，否则会超过原数范围）。
pre++：已确定的 1 数增加。
如果 pre>k：已经使用的 1 超过了限额，原数不可能满足条件，提前结束。
(4) 处理完所有位的情况
if(i==0 && pre==k) cnt++;如果成功处理到最低位（i==0），并且整个过程中使用的 1 数恰好为 k，那么原数 n 本身也满足条件，需要计入。
【算法代码】
#include<bits/stdc++.h>
using namespace std;const int N=35; //数的位数
int f[N][N]; //f[i][j]表示在i个位置上放置j个1的组合数
int k,b;void init() {for(int i=0; i<N; i++)for(int j=0; j<=i; j++)if(j==0) f[i][j]=1;else f[i][j]=f[i-1][j-1]+f[i-1][j];
}int dp(int n) {if(n==0) return 0;vector<int> v;while(n) {v.push_back(n%b);n/=b;}int cnt=0,pre=0;for(int i=v.size()-1; i>=0; i--) {int x=v[i];if(x>0) {cnt+=f[i][k-pre];if(x>1) {if(k-pre-1>=0) cnt+=f[i][k-pre-1];break;} else {pre++;if(pre>k) break;}}if(i==0 && pre==k) cnt++;}return cnt;
}int main() {init();int le,ri;cin>>le>>ri>>k>>b;cout<<dp(ri)-dp(le-1)<<endl;return 0;
}/*
in:
15 20
2
2out:
3
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/156048397
https://blog.csdn.net/hnjzsyjyj/article/details/156039366
https://blog.csdn.net/hnjzsyjyj/article/details/156267002
https://blog.csdn.net/hnjzsyjyj/article/details/156011817
https://blog.csdn.net/WhereIsHeroFrom/article/details/148437243
https://www.acwing.com/solution/content/245183/