AOJ 2142 - Bitwise Kingdom

問題文 : Bitwise Kingdom

解法 :
$n$ bit 中$k$ bit が$1$ の市民の人数は$_{n}\text{C}_{k}$ 人である. よって, $_{n}\text{C}_{k} \geqq m$ となるまで$m$ を減らす.
あとは, 先頭に$1$ を入れたときに自分より速い組み合わせが幾つあるかをたどりながら$0$ か$1$ を出力していけば良い.
コード :

#include <cstdio>

using namespace std;
typedef long long int ll;

ll comb[61][61];
int n;

void getMth(int num, ll pos)
{
	for (int i = 1; i <= n; i++){
		if (num == 0) printf("0");
		else if (comb[n - i][num] >= pos) printf("0");
		else {
			printf("1");
			pos -= comb[n - i][num];
			num--;
		}
	}
	printf("\n");
}

int main()
{
	for (int i = 0; i <= 60; i++){
		comb[i][0] = comb[i][i] = 1;
		for (int j = 1; j < i; j++){
			comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
		}
	}
	
	ll m;
	while (scanf("%d %lld", &n, &m) && n){
		int i = 0;
		while (m - comb[n][i] > 0){
			m -= comb[n][i++];
		}
		getMth(i, m);
	}

	return (0);
}