链接：HDOJ3271

题意：10进制的【A，B】区间内，在转化为BASE进制之后，各个数位的和为M的有多少个数，其中第K个数是多少


思路：转为为BASE进制和转为10进制有什么太大区别吗？

因为BASE不超过10，所以就是在模板的calc函数里改个值就好了

求数位的和为M就是模板


其中第二问：第K个数是多少有点麻烦

首先呢，第1个数是calc（X-1）这样来计算

最大的那个数是calc（Y）

然后就是经典二分搞定



#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 1050
#define maxnum 1000050
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define MOD 1000000007

int BASE,M;
int digit[40];
int dp[40][500];

int dfs(int pos,int sum,bool flag){
	if (pos==0) return sum==M;
	if (flag&&dp[pos][sum]!=-1) return dp[pos][sum];
	int up=flag?BASE-1:digit[pos];
	int ans=0;
	for(int i=0;i<=up;i++){
		int temp=sum+i;
		if (temp>M) continue;
		ans+=dfs(pos-1,temp,flag||i<up);
	}
	if (flag) dp[pos][sum]=ans;
	return ans;
}

int calc(int num){
	if (num<0) return 0;
	int len=0;
	while(num){
		digit[++len]=num%BASE;
		num/=BASE;
	}
	return dfs(len,0,0);
}

int main(){
	//input;
	int Q,X,Y,K,Case=0;
	while(scanf("%d",&Q)!=EOF){
		printf("Case %d:\n",++Case);
		memset(dp,-1,sizeof(dp));
		scanf("%d%d%d%d",&X,&Y,&BASE,&M);
		if (X>Y) swap(X,Y);
		if (Q==1)
			printf("%d\n",calc(Y)-calc(X-1));
		else{
			scanf("%d",&K);
			int l=X,r=Y+1;
			int limit=calc(X-1);
			while(l<r){
				int m=l+(r-l)/2;
				if (calc(m)-limit<K)
					l=m+1;
				else
					r=m;
			}
			if (l==Y+1)
				printf("Could not find the Number!\n");
			else
				printf("%d\n",l);
		} 
	}
	return 0;
}