题目链接：URAL1057


题意：区间【X，Y】内，有多少个数可以表示成K个不同的B的幂次方之和

如：K=2，B=2，3=2^0+2^1，5=2^2+2^0等


这个题是论文上的题：算法合集之《浅谈数位类统计问题》

其实归到数位DP不是很合适，因为数学推导推完了之后就是一个组合数的问题


详细分析见论文吧，不再赘述，说说我对代码的理解

#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxn 50
#define maxnum 1000050
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)

int x,y,k,b,C[maxn][maxn];
int digit[maxn];

int calc(int x,int k,int b){
	int len=0,ans=0;
	while(x){
		digit[++len]=x%b;
		x/=b;
	}
	for(int i=len;i>=0;i--){
		if (digit[i]>1){
			//考虑这一位不取答案是C[i-1][K] 
			//考虑这一位取，答案是C[i-1][K-1]
			//所有情况考完了，可以退出循环了 
			ans+=C[i-1][k]+C[i-1][k-1];
			break;
		}
		else if (digit[i]==1){
			//考虑这一位不取的情况 
			ans+=C[i-1][k];
			k--;
		}
		if (k<0) return ans;
	}
	return ans;
}

int main(){
	//input;
	C[0][0]=1;
	for(int i=1;i<=40;i++){
		C[i][0]=C[i-1][0];
		for(int j=1;j<=i;j++)
			C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
	scanf("%d%d%d%d",&x,&y,&k,&b);
	cout<<calc(y+1,k,b)-calc(x-1+1,k,b)<<endl;
	return 0;
}