好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

题目描述

原题来自：NEERC 2000 Central Subregional，题面详见 Ural 1057。

求给定区间 $[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

样例解释

$X=15, Y=20, K=2, B=2$，即在 $[15,20]$ 中寻找可以表示为两个不同的 $2$ 的幂次之和的数。

• $15 = 2^3+2^2+2^1+2^0$（4个幂次，不符合 $K=2$）
• $16 = 2^4$（1个幂次，不符合）
• $17 = 2^4+2^0$（符合）
• $18 = 2^4+2^1$（符合）
• $19 = 2^4+2^1+2^0$（3个幂次，不符合）
• $20 = 2^4+2^2$（符合）

因此共 $3$ 个数。

数据范围

对于全部数据：

• $1 \le X \le Y \le 2^{31}-1$
• $1 \le K \le 20$
• $2 \le B \le 10$

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

提示
此题为 数位 DP 问题，可以转化为 B 进制下数位 1 的个数为 K 且所有位只能是 0 或 1 的问题。

原因：一个数可以表示为 $K$ 个互不相等的 $B$ 的整数次幂之和，等价于该数在 $B$ 进制表示下，每一位只能是 $0$ 或 $1$，且所有位中 $1$ 的个数恰好为 $K$。
因为 $B$ 进制下，每一位的权重是 $B^i$，如果某位是 $c$（$0 \le c < B$），则相当于 $c$ 个 $B^i$ 相加；但题目要求每个幂次只能用一次（即不能合并），所以 $c$ 只能为 $0$ 或 $1$。

注意：如果 $B>2$，则 $c$ 只能为 $0$ 或 $1$，如果出现 $c \ge 2$，则该数无法表示为题目要求的形式。

因此问题转化为：求 $[X,Y]$ 中，在 $B$ 进制下，每一位都是 $0$ 或 $1$，且 $1$ 的个数恰好为 $K$ 的数的个数。

方法：

1. 将 $n$ 转换为 $B$ 进制，得到数位数组 $a[0 \dots m-1]$（最高位为 $a_{m-1}$）；
2. 设计数位 DP 状态 $dp[pos][cnt][limit]$：处理到第 $pos$ 位（从高到低），已经填了 $cnt$ 个 $1$，$limit$ 表示是否受上限限制；
3. 转移时，当前位只能填 $0$ 或 $1$，且如果 $limit=1$，则不能超过 $a[pos]$；
4. 最终 $dp[0][K][1]$ 即为不超过 $n$ 的满足条件的数的个数。

答案即为 $calc(Y) - calc(X-1)$。

复杂度：状态数 $O(\log_B Y \cdot K)$，可以接受。

注意：当 $B>2$ 时，如果某一位 $a[pos] \ge 2$，则从该位开始，如果不取 $limit$，后面的位可以任填 0 或 1（因为已经小于上限），可以直接用组合数计算剩余位的方案数，从而加速。