1064.cpp

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

/* This Code is Submitted by wywcgs for Problem 1064 on 2006-11-11 at 12:53:35 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int DN = 32, N = 201;
const int F = 1000, FK = 3;
 
class BigInt {
private:
	int n[DN], len;
public:
	BigInt(int e = 0) : len(1) { memset(n, 0, sizeof(n)); n[0] = e; }
	void operator +=(const BigInt&);
	BigInt operator +(const BigInt& b) const { BigInt r = *this; r += b; return r; }
	void operator -=(const BigInt&);
	BigInt operator -(const BigInt& b) const { BigInt r = *this; r -= b; return r; }
	void operator *=(const BigInt&);
	BigInt operator *(const BigInt& b) const { BigInt r = *this; r *= b; return r; }
	void operator *=(int);
	BigInt operator *(int k) const { BigInt r = *this; r *= k; return r; }
	void operator /=(int);
	BigInt operator /(int k) const { BigInt r = *this; r /= k; return r; }
	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;
}
void BigInt::operator -=(const BigInt& b) {
	for(int i = 0; i < len; i++) {
		n[i] -= b.n[i];
		if(n[i] < 0) { n[i] += F; n[i+1]--; }
	}
	while(len > 1 && n[len-1] == 0) len--;
}
void BigInt::operator *=(const BigInt& b) {
	BigInt a = *this;
	memset(n, 0, sizeof(n)); len = a.len+b.len;
	for(int i = 0; i < a.len; i++)
		for(int j = 0; j < b.len; j++)
			n[i+j] += a.n[i]*b.n[j];
	for(int i = 0; i < len; i++) {
		if(n[i] < F) continue;
		n[i+1] += n[i]/F; n[i] %= F;
		len >?= i+2;
	}
}
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 {
	printf("%d", n[len-1]);
	for(int i = len-2; i >= 0; i--)
		printf("%0*d", FK, 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; ) {
		BigInt r = a[n];
		int m = n >> 1;
		if(!(n&1)) r += (a[m]+BigInt(1))*a[m]/2;
		for(int i = 1; i <= m; i++) r -= a[i]*a[n-i];
		r.print();
	}
	
	return 0;
}