记录编号	194880	评测结果	AAAAAAAAAA
题目名称	分裂	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.612 s
提交时间	2015-10-17 16:25:18	内存使用	60.13 MiB

#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>

using namespace std;
//typedef unsigned long long bign;
const long long MAXN(10010);
struct bign{
    static const int MO = 10000;
    long len, num[1010];
    bign(){
        len = 1;
        memset(num, 0, sizeof(num));
    }
    bign operator* (const int &he){
		bign c, a = *this;
		c.len = a.len;
		int g = 0;
		for (int i = 0; i < c.len; i++){
			g += a.num[i] * he;
			c.num[i] = g % MO;
			g /= MO;
		}
		while (g){
			c.num[c.len++] = g % MO;
			g /= MO;
		}
		return c;
    }
    bign operator- (const bign &he){
		bign c, a = *this;
		c.len = a.len;
		for (int i = 0; i < c.len; i++)
			if (a.num[i] < he.num[i]) {
				a.num[i + 1]--, a.num[i] += MO;
				c.num[i] = a.num[i] - he.num[i];
			}
			else
				c.num[i] = a.num[i] - he.num[i];
		while (c.len > 1 && !c.num[c.len - 1])
			c.len--;
		return c;
    }
    bign operator-= (const bign &he){
        return *this = *this - he;
    }
    bign operator/ (const int &he){
		bign c, a = *this;
		c.len = a.len;
		int temp = 0;
		for (int i = c.len - 1; i >= 0; i--){
			temp = temp * MO + a.num[i];
			c.num[i] = temp / he;
			temp %= he;
		}
		while (c.len > 1 && !c.num[c.len - 1])
			c.len--;
		return c;
    }
}	cat[5501], ans[MAXN];

ostream& operator<< (ostream &out, const bign &he){
	printf("%d", he.num[he.len - 1]);
	for (int i = he.len - 2; i >= 0; --i)
		printf("%04d", he.num[i]);
	return out;
}

long long n;

main()
{
	freopen("mushroom.in", "r", stdin);
//	cout << sizeof(ans) / 1024.0 / 1024.0 << endl;
	cin >> n;
	
	cat[2].num[0] = 1, cat[3].num[0] = 1;
	for (long long i = 4; i <= n / 2 + 2; ++i)
		cat[i] = cat[i - 1] * (4 * (i - 1) - 6) / (i - 1);
	ans[1].num[0] = 1;
	for (long long i = 2; i <= n; ++i){
		ans[i] = ans[i - 1] * 2;
		if (i & 1)
			ans[i] -= cat[(i + 3) >> 1];
//		cout << ans[i] << endl;
	}
	
	freopen("mushroom.out", "w", stdout);
	cout << ans[n];
//	for (; ; );
}