题目 1117: K-进制数

解题思路:

本题采用排列组合的方式，保证严格递增，以题目为例，共七位，分为三组；

1. 最高位为0时，只需要后两位严格递增即可，如何保证呢，从范围内抽取两个数即可满足，抽取两个数，我们就指定它用递增方式去放。所以我们只需要满足从1-7中抽取两个数即可满足。

2. 最高位不为0时，可以采用for循环遍历的方式，遍历最高位的值。指定最高位，后两位用排列组合的方式，不过后两位的范围要对应发生更改，只需要用上面的范围减去最高位的值，抽取的位数保持不变。

注意事项:

       排列组合的关键点在于：我们不需要去满足严格递增，因为当我们从几个数中，抽出两个数时，这个数就有一种情况来满足题目所需，即我们讲抽出来的数，按照要求放好即可，那么就转变成了抽取有多少种情况，即排列组合。

       除此之外，我们还需要去考虑，是否整除，如果整除，则不需要考虑最高位，因为最高位和其它没有什么区别，当不整除时，由于高位与低位的范围不一致，所以分开进行考虑。

下面是组合的代码：

int jiecheng(int x){//阶乘
	long long ret=1;
	for(int i=x;i>0;i--){
		ret *=i;
		
	}
	return ret;
}

int c(int x,int y){//组合
	
	long long int ret=0;
	
	ret=jiecheng(x)/jiecheng(y)/jiecheng(x-y);
	return ret;
}

参考代码:

#include<bits/stdc++.h>
using namespace std;

int jiecheng(int x){
	long long ret=1;
	for(int i=x;i>0;i--){
		ret *=i;
		
	}
	return ret;
}

int c(int x,int y){
	
	long long int ret=0;
	
	ret=jiecheng(x)/jiecheng(y)/jiecheng(x-y);
	return ret;
}
int main(){
	int k,w;
	cin>>k>>w;
	int wei=w/k;
	int max=pow(2,k)-1;
	int zui=pow(2,w%k)-1;
	long long int sum=0;
	//最高位是0,或正好w/k整除

	if(w%k){
		for(int i=2;i<=wei;i++){
			sum+=c(max,i);
		
		} 
		for(int i=1;i<=zui;i++){
			sum+=c(max-i,wei);
		}
	}
	
	if(w%k==0){
		for(int i=2;i<=wei;i++){
			sum+=c(max,i);
		} 
		
	}
	 cout<<sum;
	
	
	
	
	
	
	return 0;
}