题目链接

可以对题意进行转换，K个不相等的B的整数幂次 可转换为 B进制下有K个1，问题就变成求在区间$[X,Y]$有几个数 在B进制下1的个数恰好为K。

求某个区间内满足某种性质的数的个数，常常用数位DP来解。数位DP常用俩技巧：
1、若能求得$f[n]$是$[0,n]$满足该性质的数的个数，那么答案就是$f[Y]-f[X-1]$
2、用树来考虑问题

不妨设这个数为$N$，$N$从低到高每位分别是$a_1,a_2,a_3,...,a_n$
例如$N=6543$，$a_1=3,a_2=4,a_3=5,a_4=6$

---

下面以$N=6543$，十进制（$B=10$），$K=3$为例，求$[0,6543]$中符合条件的数字数目。

• 考虑$a_n$位的数字$x$，利用$0\le x\le 5,x=6$可将区间$[0,6543]$拆成两部分：$[0,5999]$、$[6000,6543]$
  • 对于$0\le x\le 5$，那么代表区间$[0,5999]$，可能的解只有$1110,1101,1011,0111$。
    • 具体求法可看$x$是否为1：
      若$x=1$，也就是1 _ _ _ ，后面只有3个空位，且只能选2个1，那么就是$C_3^2$;
      若$x\ne 1$ ，后面有3个空位，能选3个1，那么就是$C_3^3$;
      因此总共合法的数就是$C_3^2+C_3^3=4$
    • 换成一般的情况就是
      若$0\le x\le a_i-1$，$a_i$前面$a_{i+1},a_{i+2},...,a_n$已经用了$last$个1，那么满足条件的数可以直接求出：$C_{i-1}^{k-last-1}+C_{i-1}^{k-last}$
      这边$i=n$是第一位，所以$last=0$
  • 对于$x=6$，那么代表区间$[6000,6543]$，如果区间合法，需要继续看下一位$a_{n-1}$。这边题目要求只能取0或1，6xxx的数字不可能是解，所以6是不合法的，不用接着往下看，退出循环。
    • 换成一般的情况就是$x=a_i$，且区间合法：$a_i=1$（$last+1$）或$a_i=0$（$last$不变）。继续看下一位$a_{i-1}$，否则退出。

---

以$N=1010$，十进制（$B=10$），$K=2$为例，求$[0,1010]$中符合条件的数字数目。

• 考虑$a_4$位的数字$x$，利用$0\le x\le a_4-1,x=a_4=1$可将区间$[0,1010]$拆成两部分：
  • 对于$0\le x\le 0$，那么代表区间$[0000,0999]$，$C_3^2=3$（x不能选1，所以只有$C_{i-1}^{k-last}$，分别是0011、0101、0110）。
  • 对于$x=1$，那么代表区间$[1000,1010]$，$a_n=1$，区间合法，$last=1$，继续看下一位$a_3$。
• 考虑$a_3$的数字$x$，利用$0\le x\le a_3-1,x=a_3=0$可将区间$[1000,1010]$拆成两部分：
  • $0\le x\le -1$，非法区间$[1000,1(-1)10]$
  • $x=0$，合法区间$[1000,1010]$，$last$不变，继续看下一位$a_2$
• 考虑$a_2$的数字$x$，利用$0\le x\le a_2-1,x=a_2=1$可将区间$[1000,1010]$拆成两部分：
  • $0\le x\le 0$，合法区间$[1000,1009]$，$C_{i-1}^{k-last}=C_1^1=1$（1001）
  • $x=1$，合法区间$[1010,1010]$，$last$不变，继续看下一位$a_1$
• 考虑$a_1$的数字$x$，利用$0\le x\le a_1-1,x=a_1=0$可将区间$[1010,1010]$拆成两部分：
  • $0\le x\le -1$，非法区间$[1010,101(-1)]$
  • $x=0$，合法区间$[1010,1010]$，没有下一位了，直接判断N是否合法

---

综上流程就三句话

• 考虑$a_i$位的数字$x$，利用$0\le x\le a_i-1,x=a_i$可将区间$[a_n{a}_{n-1}...a_i...a_1,N]$拆成两部分：$[a_n{a}_{n-1}...a_i...a_1,a_n{a}_{n-1}...a_{i}0...0-1]$、$[a_n{a}_{n-1}...a_{i}0...0,N]$。
  • 若$0\le x\le a_i-1$：$a_i$前面$a_{i+1},a_{i+2},...,a_n$已经用了$last$个1，那么满足条件的数可以直接求出：ans+=$C_{i-1}^{k-last-1}+C_{i-1}^{k-last}$（如果$a_i=1$则只有$C_{i-1}^{k-last}$，如果$a_i=0$则ans不变）
  • 若$x=a_i$，且区间合法：$a_i=1$（$last+1$）或$a_i=0$（$last$不变），继续看下一位$a_{i-1}$，否则退出（当然$last>K$也要退出）。如果没有下一位了，直接判断N是否合法（$last=K$），若合法ans+=1。

数位DP模板如下：

int dp(int n) {if (!n) return 0; // 非法边界 vector<int> nums;while(n) nums.push_back(n % B), n /= B; // 将数按位分解 int res = 0; // 问题答案 int last = 0; // 向下走时父亲的信息(此题是使用了多少个1)for (int i = num.size() - 1; i >= 0; i --) { // 最高位向最低位枚举 int x = nums[i];}return res;
} int main() {printf("%d\n", dp[Y] - dp[X - 1]);return 0;
}

本题代码：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;const int N = 35;int X, Y, K, B;
int C[N][N]; //C[n, m] n个里选m个 void init(int n) {C[1][1] = C[1][0] = 1;for (int i = 2; i <= n; i ++ ) {C[i][0] = 1;for (int j = 1; j <= i; j ++ ) C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; }
}int dp(int n) {if (!n) return 0; // 非法边界 vector<int> nums;while(n) nums.push_back(n % B), n /= B; // 将数按位分解 int res = 0; // 问题答案 int last = 0; // 向下走时父亲的信息(此题是使用了多少个1)for (int i = nums.size() - 1; i >= 0 ; i -- ) { // 最高位向最低位枚举 int x = nums[i];if (x == 1) {res += C[i][K - last];last ++;if(last > K) break;}else if (x > 0) {res += C[i][K - last];if (K - last - 1 >= 0)  res += C[i][K - last - 1];break;}if(!i && last == K) res ++ ;}return res;
} int main() {scanf("%d%d%d%d", &X, &Y, &K, &B);init(N - 1);printf("%d\n", dp(Y) - dp(X - 1));return 0;
}