记录编号	142726	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]R集合	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.788 s
提交时间	2014-12-10 17:17:49	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEL=150;
const int BASE=10000;
class HPint{//要确保高位之后全0
public:
	int len;
	int s[SIZEL];
	void print(void){
		printf("%d",s[len-1]);
		for(int i=len-2;i>=0;i--) printf("%.4d",s[i]);
	}
	HPint(int x=0){
		len=1;
		memset(s,0,sizeof(s));
		s[0]=x;
	}
};
HPint operator + (HPint a,HPint b){//高精+高精
	int i;
	a.len=max(a.len,b.len);
	for(i=0;i<a.len||a.s[i];i++){
		a.s[i]+=b.s[i];
		a.s[i+1]+=a.s[i]/BASE;
		a.s[i]%=BASE;
	}
	if(i>a.len) a.len=i;
	while(a.len>1&&!a.s[a.len-1]) a.len--;
	return a;
}
HPint operator - (HPint a,HPint b){//高精-高精,要求b.s在最高位之后都是0
	for(int i=0;i<a.len;i++){
		a.s[i]-=b.s[i];
		while(a.s[i]<0) a.s[i+1]--,a.s[i]+=BASE;
	}
	while(a.len>1&&!a.s[a.len-1]) a.len--;
	return a;
}
HPint operator * (HPint a,HPint b){//高精*高精
	HPint c;
	c.len=a.len+b.len+1;
	for(int i=0;i<a.len;i++){
		for(int j=0;j<b.len;j++){
			c.s[i+j]+=a.s[i]*b.s[j];
			c.s[i+j+1]+=c.s[i+j]/BASE;
			c.s[i+j]%=BASE;
		}
	}
	while(c.len>1&&!c.s[c.len-1]) c.len--;
	return c;
}
HPint operator * (HPint a,int b){//高精*单精
	int i;
	for(i=0;i<a.len;i++) a.s[i]*=b;
	for(i=0;i<a.len||a.s[i];i++){
		a.s[i+1]+=a.s[i]/BASE;
		a.s[i]%=BASE;
	}
	if(i>a.len) a.len=i;
	while(a.len>1&&!a.s[a.len-1]) a.len--;
	return a;
}
HPint operator / (HPint a,int b){//高精/单精
	for(int i=a.len-1;i>=0;i--){
		if(i>0) a.s[i-1]+=(a.s[i]%b)*BASE;
		a.s[i]/=b;
	}
	while(a.len>1&&!a.s[a.len-1]) a.len--;
	return a;
}
HPint calc_C(int n,int m){//n选m的组合数
	HPint ans=1;
	for(int i=0;i<m;i++)
		ans=ans*(n-i)/(i+1);
	return ans;
}
HPint Catalan(int n){
	return calc_C(2*n,n)/(n+1);
}
int main(){
	freopen("rset.in","r",stdin);
	freopen("rset.out","w",stdout);
	int n;
	HPint ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n/2;i++)
		ans=ans+calc_C(n,2*i)*(calc_C(2*i,i)/2-Catalan(i));
	ans.print();printf("\n");
	return 0;
}