VN_ZR_I - Số không (I)

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include "stdio.h"
#include "string.h"

	int n, k;
	int a[40], b[40];
	long long result;
	long C[33][33];
	
	void tinh(int i,int sk) {
		for(int j=0;j<=i;++j) {
			if(j+sk>0) result += C[j][i] * ((j+sk-1)/k+1);
		}
	}
	
	void duyet(int i, int sk) {
		if(i<0) {
			if(sk>0) result += (sk-1)/k + 1;
			return;
		}
		bool nhohon = false, lonhon = false;
		for(int j=33;j>i;--j) {
			if(a[j]>b[j]) {
				nhohon = true;
				break;
			}
			if(a[j]<b[j]) {
				lonhon = true;
				break;
			}
		}
		if(nhohon) { tinh(i+1,sk); return; }
		if(lonhon) return;
		b[i] = 0;
		duyet(i-1,sk+1);
		if(a[i]==1) {
			b[i] = 1;
			duyet(i-1,sk);
		}
	}
	
	void run() {
		memset( a, 0, sizeof(a));
		memset( b, 0, sizeof(b));
		int last=-1;
		for(int i=0;i<31;++i) if((n&(1<<i))!=0) { a[i] = 1; last = i; }
		
		result = 0;
		for(int i=last;i>=0;--i) {
			memset( b, 0, sizeof(b));
			b[i] = 1;
			duyet(i-1,0);
		}
		
		printf("%lld\n",result);
	}
	
	void init() {
		C[0][0] = 1;
		for(int i=1;i<33;++i) {
			C[0][i] = C[i][i] = 1;
			for(int j=1;j<i;++j) C[j][i] = C[j-1][i-1] + C[j][i-1];
		}
	}
	
	int main() {
		init();
		while(true) {
			n = -11;
			scanf("%d%d",&n,&k);
			if(n==-11) break;
			run();
		}
	}

Download