分析来自Moon_light 的题解，我就不重复了。主要是添加一点注释方便理解代码。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 32;  // B >= 2；也就是说这个数最多有可能被表示成二进制数，而这个数得最大值是2^31-1所以，要多开几位

int K, B;
int f[N][N];

// 求组合数其实也是一种DP：f[i][j] : 从i个数里面选j个，一共有多少种选法
// 固定一个数a，左边是选a的所有集合，右边是不选a的所有集合
// 选a：f[i - 1][j - 1] 选了一个a了，现在只需要i-1个数里面选，从剩下的j-1个数里面选i-1个
// 不选a: f[i - 1][j] 依然还是要在剩下的i-1个数中选j个数
void init(){
    for(int i = 0; i < N; i ++)
        for(int j = 0; j <= i; j ++){
            if(!j)  // 如果j=0，那么就是从i个数里面选0个数，也就是什么也不选，只有一种选法
                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;  // K是大于0的，那么如果n=0肯定是一个数都不包含

    vector<int> nums;  // 将n表示成B进制数
    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){  // x > 0求左分支中的数的个数,如果x = 0的话i位上只能取0，直接从下一位开始看
            res += f[i][K - last];  // 由于x是大于0的，所以第i位选0的话，i-1位可以随便选，不会超过0111..111不会超过x000...000
            if(x > 1){  // x > 1的话表示i位就算全选1:111111也不会超过x000...000，可以随便选
                if(K - last - 1 > 0) res += f[i][K - last - 1];
                break;
            }else{  // x == 1 不能随便选了，因为选出来的数有可能超出范围
                last ++;  // 选一个1，到下一位继续去选
                if(last > K) break;
            }
        }
        // 对最后一位的特殊处理，最后一位要么大于1，要么等于1，要么等于0，
        // 等于0就不用管了
        // 如果大于1的话，上面的公式会计算出来
        // 如果等于1的话，按照上面的循环是要走下一轮的，但是因为是最后一位，所以这个1肯定是能取得，就不用再执行下一轮了，直接+1
        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;
}