1063.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1063 on 2006-08-16 at 00:16:54 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int DN = 32, N = 201;
const int F = 1000;

class BigInt {
private:
	int n[DN], len;
public:
	BigInt(int e = 0) : len(1) { memset(n, 0, sizeof(n)); n[0] = e; }
	BigInt operator *(int k) const { BigInt r = *this; r *= k; return r; }
	BigInt operator *(const BigInt&) const;
	BigInt operator +(const BigInt& b) const { BigInt r = *this; r += b; return r; }
	void operator +=(const BigInt&);
	void operator *=(int);
	void operator /=(int);
	void print() const;
};
void BigInt::operator +=(const BigInt& b) {
	len >?= b.len;
	int r = 0;
	for(int i = 0; i < len; i++) {
		n[i] += r+b.n[i];
		r = n[i]/F; n[i] %= F;
	}
	if(r != 0) n[len++] = r;
}
BigInt BigInt::operator *(const BigInt& b) const {
	BigInt r(0);
	for(int i = 0; i < len; i++)
		for(int j = 0; j < b.len; j++)
			r.n[i+j] += n[i]*b.n[j];
	r.len = len+b.len;
	for(int i = 0; i < r.len; i++) {
		if(r.n[i] < F) continue;
		r.n[i+1] += r.n[i]/F; r.n[i] %= F;
		r.len >?= i+2;
	}
	return r;
}
void BigInt::operator *=(int k) {
	int r = 0;
	for(int i = 0; i < len; i++) {
		n[i] = n[i]*k+r;
		r = n[i]/F; n[i] %= F;
	}
	if(r != 0) n[len++] = r;
}
void BigInt::operator /=(int k) {
	int r = 0;
	for(int i = len-1; i >= 0; i--) {
		n[i] += r*F;
		r = n[i]%k; n[i] /= k;
	}
	while(len > 1 && n[len-1] == 0) len--;
}
void BigInt::print() const {
	for(int i = len-1; i >= 0; i--)
		if(i == len-1) printf("%d", n[i]);
		else printf("%03d", n[i]);
	putchar('\n');
}

BigInt s[N][N], a[N];

int main()
{
	a[1] = BigInt(1);
	for(int i = 1; i < N; i++) {
		for(int j = 1; j <= i; j++) {
			s[i][j] = s[i-j][j]+a[i+1-j];
			a[i+1] += a[j]*s[i][j]*j;
		}
		a[i+1] /= i;
	}
	for(int n; scanf("%d", &n) != EOF && n != 0; ) a[n].print();
	
	return 0;
}