POJ 2084

第一题组合数学题。可以使用递推，设1与其他各数分别连边，假设N=3;若1-4，则圆分成两部分计数，此时可以利用乘法原理。（高精度）

#include <cstdio>

#include <cstring>

#include <iostream>

#include <string>

using namespace std;

const int maxn = 200;

struct bign {

	int len, s[maxn];

	bign() {

		memset(s, 0, sizeof(s));

		len = 1;

	}

	bign(int num) {

		*this = num;

	}

	bign(const char* num) {

		*this = num;

	}

	bign operator =(int num) { //直接以整数赋值

		char s[maxn];

		sprintf(s, "%d", num);

		*this = s;

		return *this;

	}

	bign operator =(const char* num) { //以字符串赋值

		len = strlen(num);

		for(int i = 0; i < len; i++)

			s[i] = num[len - i - 1] - '0';

		return *this;

	}

	string str() const { //将bign转化成字符串

		string res = "";

		for(int i = 0; i < len; i++)

			res = (char) (s[i] + '0') + res;

		if(res == "")

			res = "0";

		return res;

	}

	bign operator +(const bign& b) const { //重载+号运算

		bign c;

		c.len = 0;

		for(int i = 0, g = 0; g || i < max(len, b.len); i++) {

			int x = g;

			if(i < len) x += s[i];

			if(i < b.len) x += b.s[i];

			c.s[c.len++] = x % 10;

			g = x / 10;

		}

		return c;

	}

	void clean() { //去掉前到0

		while(len > 1 && !s[len - 1])

			len--;

	}

	bign operator *(const bign& b) { //重载*号运算

		bign c;

		c.len = len + b.len;

		for(int i = 0; i < len; i++)

			for(int j = 0; j < b.len; j++)

				c.s[i + j] += s[i] * b.s[j];

		for(int i = 0; i < c.len - 1; i++) {

			c.s[i + 1] += c.s[i] / 10;

			c.s[i] %= 10;

		}

		c.clean();

		return c;

	}

	bign operator -(const bign& b) { //重载-号运算

		bign c;

		c.len = 0;

		for(int i = 0, g = 0; i < len; i++) {

			int x = s[i] - g;

			if(i < b.len)

				x -= b.s[i];

			if(x >= 0)

				g = 0;

			else {

				g = 1;

				x += 10;

			}

			c.s[c.len++] = x;

		}

		c.clean();

		return c;

	}

	bool operator <(const bign& b) const { //重载<号运算

		if(len != b.len)

			return len < b.len;

		for(int i = len - 1; i >= 0; i--)

			if(s[i] != b.s[i])

				return s[i] < b.s[i];

		return false;

	}

	bool operator >(const bign& b) const { //重载>号运算

		return b < *this;

	}

	bool operator <=(const bign& b) { //重载<=号运算

		return !(b > *this);

	}

	bool operator ==(const bign& b) { //重载>=号运算

		return !(b < *this) && !(*this < b);

	}

	bign operator +=(const bign& b) { //重载+=号运算

		*this = *this + b;

		return *this;

	}

};

istream& operator >>(istream &in, bign& x) { //重载输入运算符

	string s;

	in >> s;

	x = s.c_str();

	return in;

}

ostream& operator <<(ostream &out, const bign& x) { //重载输出运算符

	out << x.str();

	return out;

}

bign ans[210];

void initial(){

	ans[2]=1;

	ans[4]=2;

	for(int i=5;i<=200;i++){

		ans[i]=ans[i-2]+ans[i-2];

		for(int j=3;j<i;j++){

			ans[i]=ans[i]+ans[j-2]*ans[i-j];

		}

	}

}

int main(){

	initial();

	int n;

	while(scanf("%d",&n),n!=-1){

		cout<<ans[2*n]<<endl;

	}

	return 0;

}