• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 【卡特兰数+高精度】hdu3723

3小时前 1次浏览

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<set>
#include<map>
#include<cmath>
using namespace std;

typedef long long ll;
const ll yaw = 100000;
struct gjd{
int len;
ll a[10000]; //5*20
//0-->19 useful
}A,ANS;
void mul(gjd &x,ll y) {
for(int i=0;i<=x.len;i++) x.a[i]*=y;
for(int i=0;i<=x.len;i++) {
if(x.a[i]>=yaw) {
x.a[i+1] += x.a[i]/yaw;
x.a[i]%=yaw;
}
if(x.a[x.len+1]) x.len++;
}
}
void div(gjd &x,ll y) {
ll o = 0;
for(int i=x.len;i>=0;i--) {
ll oo = x.a[i];
x.a[i] = (o*yaw+oo)/y;

o = (o*yaw+oo)%y;
}
while(x.len&&(!x.a[x.len])) x.len--;
}
void pint(gjd &x) {
if(x.len<=19) {
printf("%lld",x.a[x.len]);
for(int i=x.len-1;i>=0;i--) {
printf("%05lld",x.a[i]);
}
} else {
cerr<<"fuck";
printf("%lld",x.a[19]);
for(int i=18;i>=0;i--) {
printf("%05lld",x.a[i]);
}
}
}
int le = max(x.len,y.len);
for(int i=0;i<=le;i++) {
x.a[i] += y.a[i];
x.a[i+1] += x.a[i]/yaw;
x.a[i] %= yaw;
}
x.len = le;
while(x.a[x.len+1]) x.len++;
}
int main(){
/*
A.a[0] = 11;
mul(A,300000);
ANS.len = 2;
ANS.a[2] = 3;
pint(A);
*/
A.a[0]=1; ANS.a[0]=1;
ll n; scanf("%lld",&n);
for(ll i=1;i*2<=n;i++) {
ll cf = (n-2*i+1ll)*(n-2*i+2ll);
mul(A, cf);
div(A,i*(i+1));
}
pint(ANS);
return 0;
}
``````