难点

还是动规方程的书写，状态表示在b进制下，枚举到第i位，并且当前剩余的可加的数的数量k
k:如果当前这个数在b进制下的数为0，则不要，如果不为0，则要

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

using namespace std;

const int N=35;//2进制数最大能到21位
int k,B;
int f[N][N];//表示从a位数里选b个数是1的方案数

void init()
{
    for(int i=0;i<N;i++)
       for(int j=0;j<=i;j++)
         if(!j)  f[i][j]=1;   //
         else f[i][j]=f[i-1][j]+f[i-1][j-1];        //根据最后一位数是不是1来进行状态分析
}

int dp(int n)   //求出从0到n满足要求的数的个数
{
    if(!n)  return 0;    //边界条件
    vector<int> nums;
    while(n)  nums.push_back(n%B),n/=B;  //转换位b进制
    int res=0;
    int last=0;
     //当前这个转换为b进制之后，len为size(),并且每一位的大小在0-(b-1)之间
    for(int i=nums.size()-1;i>=0;i--) 
    {
        int x=nums[i];//为当前的状态
            //当x为真          
        //直接排除了为0的状态，也就是说这个数在进行装换的时候不能转换为这个进制的k次幂
        if(x)  
        {
            res+=f[i][k-last];          //表示为这个数在哪一位置上，并且在到达这个数之前一共用了多少个数
            if(x>1)
            {
                if(k-last-1>=0)  res+=f[i][k-last-1];
                break;
            }
            else //也就是x小于等于1，也就是说x的值为1
            {
                last++;   //总位数++
                if(last>k)  break;      //如果组成这个数的个数的b进制下的数大于规定的数，break
            }
        }
        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;
}