1980.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 103 行

/*  This Code is Submitted by wywcgs for Problem 1980 on 2005-10-27 at 17:18:34 */ 
#include <cstdio>
#include <cstring>

const int MAX = 64;
const int LIMIT = 100000;
const int N_MAX = 128;

class BigInt {
private:
	long long n[MAX];
	int getLen(int k) {
		int i;
		for(i = 0; k != 0; i++) {
			k /= 10;
		}
		return i;
	}
public:
	BigInt() {
		memset(n, 0, sizeof(n));
	}
	void set(int i) {
		n[0] = i;
	}
	void operator+=(const BigInt& bi) {
		int i;
		for(i = 0; i < MAX; i++) {
			n[i] += bi.n[i];
			if(n[i] >= LIMIT) {
				n[i+1] += n[i] / LIMIT;
				n[i] %= LIMIT;
			}
		}
	}
	void operator=(const BigInt& bi) {
		int i;
		for(i = 0; i < MAX; i++) {
			n[i] = bi.n[i];
		}
	}
	void operator*=(const BigInt& bi) {
		int i, j, k;
		BigInt b;
		for(i = 0; bi.n[i] != 0; i++) {
			for(j = 0; n[j] != 0; j++) {
				b.n[i+j] += bi.n[i] * n[j];
				for(k = 0; b.n[i+j+k] >= LIMIT; k++) {
					b.n[i+j+k+1] += b.n[i+j+k] / LIMIT;
					b.n[i+j+k] %= LIMIT;
				}
			}
		}
		*this = b;
	}
	void print() {
		bool begin = false;
		int len, i, j;
		for(i = MAX - 1; i >= 0; i--) {
			if(n[i] == 0) {
				if(begin) {
					printf("00000");
				}
			} else {
				if(begin) {
					len = 5 - getLen(n[i]);
					for(j = 0; j < len; j++) {
						putchar('0');
					}
				} else {
					begin = true;
				}
				printf("%lld", n[i]);
			}
		}
		putchar('\n');
	}
};

int main()
{
	BigInt big[N_MAX], p;
	int i, j, n;
	
	big[0].set(1);
	for(i = 1; i < N_MAX; i++) {
		for(j = 0; j < i; j++) {
			p = big[j];
			p *= big[i-j-1];
			big[i] += p;
		}
	}
	while(scanf("%d", &n) == 1) {
		if(n == -1) {
			return 0;
		} else {
			big[n].print();
		}
	}
	
	return 0;
}