C++ :

#include<bits/stdc++.h>
using namespace std;
const int N=35;
int f[N][N]; //f[i][j] 表示i个数中选j个1的方案数
int l,r,K,B;
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-1]+f[i-1][j];
				//第i位选1，第i位不选1 
		}
	}
}
int dp(int n)
{
	if(n==0) return 0; //0不可以表示成任何数的正整次幂
	vector<int> nums;
	while(n)
	{
		nums.push_back(n%B);
		n/=B;	
	}
	int res=0,last=0;//last 表示已经选了的1的个数
	for(int i=nums.size()-1;i>=0;i--)
	{
		int x=nums[i];
		for(int j=0;j<x;j++)
		{
			if(j==0&&K-last>=0) //0
			{
				res+=f[i][K-last];
			}
			if(j==1&&K-last-1>=0) //1
			{
				res+=f[i][K-last-1];
			}
			if(j>=2) break; //不满足 
		}	
		if(x>=2) break; //不满足
		if(x==1) last++;//继续计算下一位
		if(i==0&&K==last) res++;//这个数本身也是满足要求的 
	} 
	return res;
}
int main()
{
	cin>>l>>r>>K>>B;
	init();
	cout<<dp(r)-dp(l-1);
	return 0;
}