记录编号	554433	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	出栈序列统计	最终得分	100
用户昵称	锝镆氪锂铽	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2020-09-12 22:55:55	内存使用	0.91 MiB

#include <iostream>
#include <cstdio>
#define LL unsigned long long

using namespace std;

struct Bignum{
	int len,a[610] = {};
	void init(){
		len = 1,a[1] = 1;
	}
	void print(){
		for (int i = len;i >= 1;i --){
			printf("%d",a[i]);
		}
		printf("\n");
	}
	Bignum operator *(int b){
		Bignum c;
		int carry = 0,cur = 1;
		for (cur = 1;carry != 0 || cur == 1 || cur <= len;cur ++){
			c.a[cur] = a[cur] * b + carry;
			carry = c.a[cur] / 10;
			c.a[cur] %= 10;
		}
		c.len = -- cur;
		return c;
	}
	Bignum operator /(int b){
		Bignum c;
		int i,x = 0;
		for (i = len;i >= 1;i --){
			c.a[i] = (x * 10 + a[i]) / b;
			x = (x * 10 + a[i]) % b;
		}
		while (c.a[c.len] == 0){
			c.len --;
		}
		return c;
	}
};

Bignum Catalan(int x);

int n;
int main(void){
	freopen("stack1.in","r",stdin);
	freopen("stack1.out","w",stdout);
	scanf("%d",&n);
	Bignum e = Catalan(n);
	e.print();
	return 0;
}

Bignum Catalan(int x){   
    if (x == 1){
    	Bignum e;
    	e.init();
        return e;
    }
	else{
		Bignum ans = Catalan(x - 1);
		ans = ans * 2;
		ans = ans * (2 * x - 1);
		ans = ans / (x + 1);
		return ans;
    }
}