思路与算法

互不相同的B的幂之和，等价于B进制展开仅包含0和1，且恰有K个1。不同指数对应不同数位，不产生进位。

令F(t)表示1..t中符合条件的数的个数，答案为F(Y)-F(X-1)。把上界转换为B进制，从最高位开始递归，状态为当前位pos、还需要的1个数left、是否仍贴着上界tight。

每位只能选择0或1，并且不能超过当前允许的上界位。选1令left减1；当left<0或left>剩余位数时直接剪枝。所有位结束后，仅left=0记一种。tight=false的状态与上界无关，可按pos和left缓存。

正确性说明

B进制表示唯一，每种恰选K个不同幂的合法表示都对应唯一一个只含0/1且有K个1的数，反之亦然。前导补0不增加1的数量，也不改变数值。

递归逐位枚举所有允许的0/1选择，tight精确限制前缀不超过上界；left准确记录尚未放置的1数，剪枝只排除不可能完成的状态。因此每个合法整数计一次，非法整数不计。K≥1使全0表示自动被排除。两个前缀计数相减，恰剩闭区间内的合法数。

复杂度

设B进制位数L≤31。非受限状态有O(LK)个，每个最多两次转移，贴上界状态每层至多一个，计算O(LK)。参考程序每次前缀统计还整体初始化35×25个缓存单元，因此含初始化总时间为O(LK+35×25)，空间为35×25缓存及O(L)递归和数位数组。

易错点

上界的某位大于1时仍只能放0或1，不能把2等数字当作合法数位。X=1时要正确处理F(0)=0。K超过可用位数应立即返回0。B不是固定为2，需要先按输入的B转换上界。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int K, B;
vector<int> digit;
ll memo[35][25];
ll solve(int pos, int left, bool tight) {
    if (left < 0 || left > pos + 1)
        return 0;
    if (pos < 0)
        return left == 0;
    if (!tight && memo[pos][left] != -1)
        return memo[pos][left];
    int cap = tight ? digit[pos] : B - 1;
    ll answer = 0;
    for (int d = 0; d <= min(1, cap); ++d)
        answer += solve(pos - 1, left - d, tight && d == cap);
    if (!tight)
        memo[pos][left] = answer;
    return answer;
}
ll count(ll n) {
    if (n <= 0)
        return 0;
    digit.clear();
    while (n) {
        digit.push_back(n % B);
        n /= B;
    }
    memset(memo, -1, sizeof(memo));
    return solve(digit.size() - 1, K, true);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll x, y;
    cin >> x >> y >> K >> B;
    cout << count(y) - count(x - 1) << '\n';
}