文件详细信息

下载本文件

本文件的大小为 695 字节。

#include<cstdio>
const int maxd=32;
int x,y,K,B;
int C[maxd][maxd];
int calc(int n){
	int ans=0,cnt=0;
	for(int i=31;i>0;i--){
		if(n&(1<<i)){
			n^=1<<i;
			cnt++;
			if(cnt>K)break;
		}
		if((1<<(i-1))<=n)ans+=C[i-1][K-cnt];
	}
	if(cnt+n==K)ans++;
	return ans;
}
int change(int n){
	if(B==2)return n;
	int a[32],cnt=0;
	while(n){
		a[cnt++]=n%B;
		n/=B;
	}
	int ans=0;
	for(int i=cnt-1;i>=0;i--)
		if(a[i]==1)ans|=1<<i;
		else if(a[i]>1){
			ans|=(1<<(i+1))-1;
			break;
		}
	return ans;
}
int main(){
	for(int i=0;i<maxd;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)C[i][j]=C[i-1][j-1]+C[i-1][j];
	}
	scanf("%d%d%d%d",&x,&y,&K,&B);
	printf("%d\n",calc(change(y))-calc(change(x-1)));
	return 0;
}