题目翻译

“n恰好等于K个互不相等的B的整数次幂之和”相当于：n在B进制下由K个1和若干个0构成。
“恰好”说明不可能存在 $q*B^p$(1<q<B,p为任意自然数) ，有一位是q（1<q<B）。

AC代码及详解

#include<bits/stdc++.h>
using namespace std;
const int N=35;//x在B进制下最多有31位
int f[N][N],k,b;
void init(){//get c(i,j)
    for(int i=0;i<=N;i++)f[i][0]=1;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=f[i-1][j]+f[i-1][j-1];
}
int dp(int n){
    if(!n)return 0;
    vector<int> nums;
    while(n)nums.push_back(n%b),n/=b;
    int last=0,ans=0;
    for(int i=nums.size()-1;i>=0;i--){
        int x=nums[i];
        if(x>0){
            ans+=f[i][k-last];//如果x>0，则此位选0之后,后面可以随便选
            if(x>1){//如果x>1，则此位选1之后,后面可以随便选
                if(k-last-1>=0)ans+=f[i][k-last-1];
                break;//现在就不用遍历后面的位了,因为后面i位的所有情况都已经加在ans上了
            }else{
                //固定此位为1,之后就是遍历此位选1的情况(此位是0的所有情况都已经讨论过了)
                last++;
                if(last==k){ans++;break;}
                //if(last>k)break;//yxc的代码里是这么写的,但是其实可以直接break,因为此时一定只有一种情况了
            }
        }
        //if(i==0&&last==k)ans++;
    }
    //printf("%d\n",ans);
    return ans;
}
int main(){
    init();
    int x,y;
    scanf("%d%d%d%d",&x,&y,&k,&b);
    printf("%d",dp(y)-dp(x-1));//ans[x,y]=ans[0,y]-ans[0,x-1],这样讨论是就只用判断是否小于某值
    return 0;
}