[UVa] 10232 - Bit-wise Sequence

題目網址: http://goo.gl/CKNROF

題意:
(from luckycat)


解 法: 排列組合問題。

TAG: Math,

注意:

程式碼:

	/**
	* Tittle: 10232 - Bit-wise Sequence
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/22
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	typedef long long ll;
	// declarations
	ll n;
	ll comb[35][35];
	// functions
	// main function
	int main( void )
	{
	ll ret;
	int ones;
	// init
	clr( comb, 0 );
	comb[0][0] = 1LL;
	FOR( i, 1, 31 ) {
	comb[i][i] = comb[i][0] = 1LL;
	FOR( j, 1, i-1 )
	comb[i][j] = comb[i-1][j]+comb[i-1][j-1];
	}
	// input
	while( scanf( "%lld", &n )==1 ) {
	// solve
	ret = 0LL;
	FOR( i, 0, 31 ) {
	if( n < comb[31][i] ) {
	ones = i;
	break;
	}
	n -= comb[31][i];
	}
	for( int i=31; i>=0; --i ) {
	if( comb[i][ones] <= n ) {
	ret |= (1LL << i );
	n -= comb[i][ones];
	--ones;
	}
	}
	// output
	printf( "%lld\n", ret );
	}
	return 0;
	}

view raw 10232 - Bit-wise Sequence.cpp hosted with ❤ by GitHub