読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

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);
}