定义
这个cn啊，是组合数学里面经常会用到的东西，比如说：
- 让你算算二叉树的形态
- 又让你算算合法的括号序列
- 又或者让你算算出入栈的合法顺序
- 还可能让你去说说把多边形割成三角形方法
综上所述就是18年初赛的第8题
于是有的人弄出来了它的式子
我们设为f(n),那么有
[f(n)=sum^{n-1}_{i=0}f(i)cdot f(n-i-1)
]
当然人们并不会满足一个式子，于是就有了第二个
[f(n)=f(n-1)cdot frac{4n-2}{n+1}
]
但是因为我们没有通项式，所以必须要一个一个的算
与是通项式就来了
[f(n)=frac{C^{n}_{2n}}{n+1}
]
当然如果我们进行一点变换的话就可以得到它：
[f(n)=C^{n}_{2n}-C^{n-1}_{2n}
]
这个式子是一个好式子，面对问题是往往很容易就可以化成这一个形式，然后就发现了这是卡特兰数的题
例题
1.栈（洛谷P1044）
洛谷P1044
这一道题很容易就可以看出来这一个是Cn的模板题
那么就是这样的了
贴代码(用的是第二个式子)
//洛谷的卡特兰数模板题
#include<bits/stdc++.h>
using namespace std;
long long f[20];
void getcn(int n){
f[1]=1;
for(int i=2;i<=n;i++){
f[i]=((4*i-2)*f[i-1])/(i+1);
}
printf("%lld
",f[n]);
return ;
}
int main(){
int n;
scanf("%d",&n);
getcn(n);
return 0;
}
2.矩阵（洛谷P1722）
洛谷P1722
这一道题啊，可以看出来是一道卡特兰数的题，要求我们去模100，那么向第一个式子那样没有除法，只有加和乘的方法自然就是首选了，既然如此就用第一种方法写Cn就行了
//矩阵 洛谷P1722
#include<bits/stdc++.h>
#define Mod 100
using namespace std;
int n;
long long f[105];
void solve(){
f[0]=f[1]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<=i-1;j++){
(f[i]+=f[j]*f[i-j-1])%=Mod;
}
}
printf("%lld",f[n]);
return;
}
int main(){
scanf("%d",&n);
solve();
return 0;
}
3.树屋阶梯(洛谷P2532)
洛谷P2532
这一道题啊，首先你这么考虑，任意选中其中一阶阶梯，然后呢就把整个阶梯分成了它上面的阶梯和它右面的阶梯。每一阶阶梯都这么去考虑，写出整个式子就会发现是卡特兰数了
//洛谷P2532 树屋
//这道题不得不用高精度了
#include<bits/stdc++.h>
#define maxn 1000
using namespace std;
struct Ln{ // 整数，最大可存储一万位数字
int val[maxn];
int operator [](const int &ref)const{
return val[ref];
}
inline void Lin(){ // 读入
char S[maxn];
scanf("%s",S);
memset(val,0,sizeof(val));
int lenS=strlen(S);
val[0]=lenS;
for(int i=lenS-1,j=1;i>=0;i--,j++) val[j]=S[i]-'0';
}
inline void StrIn(char *S){
memset(val,0,sizeof(val));
int lenS=strlen(S);
val[0]=lenS;
for(int i=lenS-1,j=1;i>=0;i--,j++) val[j]=S[i]-'0';
}
inline void Lout(){ // 输出
for(int i=val[0];i>=1;i--)
putchar(val[i]+'0');
}
bool operator ==(const Ln &obj)const{ // 判断是否等于
if(val[0]!=obj[0]) return false;
for(int i=1;i<=val[0];i++) if(val[i]!=obj[i]) return false;
return true;
}
bool operator <(const Ln &obj)const{ // 判断是否小于
if(val[0]>obj[0]) return false;
if((*this)==obj) return false;
if(val[0]<obj[0]) return true;
for(int i=val[0];i>=1;i--){
if(val[i]>obj[i]) return false;
if(val[i]<obj[i]) return true;
}
return true;
}
bool operator >(const Ln &obj)const{ // 判断是否大于
Ln cmp=*this;
if(cmp < obj || cmp == obj) return false;
return true;
}
Ln operator +(const Ln &obj)const{ // 加法运算
Ln cmp;
memset(cmp.val,0,sizeof(cmp.val));
int pos=max(val[0],obj[0]),add=0;
for(int i=1;i<=pos;i++){
cmp.val[i]=val[i]+obj[i]+add;
add=cmp.val[i]/10;
cmp.val[i]=cmp.val[i]%10;
}
if(add>0) cmp.val[++pos]=add;
cmp.val[0]=pos;
return cmp;
}
Ln operator -(const Ln &obj)const{ // 减法运算 只能减出正数
Ln cmp;
memset(cmp.val,0,sizeof(cmp.val));
int pos=val[0],rent=0; // rent 借位
for(int i=1;i<=pos;i++){
cmp.val[i]=val[i]-obj[i]-rent;
if(cmp.val[i]<0) {cmp.val[i]+=10;rent=1;}
else rent=0;
}
while(cmp.val[pos]==0 && pos>1) pos--;
cmp.val[0]=pos;
return cmp;
}
Ln operator *(const int &obj)const{ // 高精度 ×低精度
// 对于高精度数 a 和低精度数 b
// 这个算法可以写成 a=a^b
Ln cmp;
memset(cmp.val,0,sizeof(cmp.val));
int pos=val[0]; // 进位
long long add=0;
for(int i=1;i<=pos;i++){
cmp.val[i]=val[i]*obj+add;
add=cmp.val[i]/10;
cmp.val[i]=cmp.val[i]%10;
}
while(add>0){
cmp.val[++pos]=add%10;
add/=10;
}
while(cmp.val[pos]==0 && pos>1) pos--;
cmp.val[0]=pos;
return cmp;
}
Ln operator *(const Ln &obj)const{ // 高精度 ×高精度
// 对于高精度数 a 和高精度 b
// 这个算法不能写成 a=a*b
Ln cmp;
memset(cmp.val,0,sizeof(cmp.val));
int pos=val[0]+obj[0];
for(int i=1;i<=val[0];i++){
for(int j=1;j<=obj[0];j++){
cmp.val[i+j-1]+=val[i]*obj[j];
cmp.val[i+j]+=cmp.val[i+j-1]/10;
cmp.val[i+j-1]=cmp.val[i+j-1]%10;
}
}
while(cmp.val[pos]==0 && pos>1) pos--;
cmp.val[0]=pos;
return cmp;
}
Ln operator /(const int &obj)const{ // 高精度 ÷低精度
Ln cmp;
memset(cmp.val,0,sizeof(cmp.val));
int pos=val[0],div=0;
for(int i=pos;i>=1;i--){
cmp.val[i]=(div*10+val[i])/obj;
div=(div*10+val[i])%obj;
}
while(cmp[pos]==0 && pos>1) pos--;
cmp.val[0]=pos;
return cmp;
}
int operator %(const int &obj)const{ // 高精度 % 低精度
int pos=val[0],div=0;
for(int i=pos;i>=1;i--) div=(div*10+val[i])%obj;
return div;
}
Ln operator /(const Ln &obj)const{ // 高精度 ÷高精度
Ln cmp,t_cmp;
memset(cmp.val,0,sizeof(cmp.val));
memset(t_cmp.val,0,sizeof(t_cmp.val));
int pos=val[0];
cmp.val[0]=1;cmp.val[1]=0;
t_cmp=cmp;
if((*this)<obj) return cmp; // 小于除数直接返回 0
for(int i=pos;i>=1;i--){
t_cmp=t_cmp*10;
t_cmp.val[1]=val[i];
int k=0;
while(t_cmp>obj || t_cmp==obj)
{
t_cmp=t_cmp-obj;
k++;
}
cmp.val[i]=k;
}
while(cmp.val[pos]==0 && pos>1) pos--;
cmp.val[0]=pos;
return cmp;
}
Ln operator %(const Ln &obj)const{ // 高精度 % 高精度
Ln t_cmp;
memset(t_cmp.val,0,sizeof(t_cmp.val));
int pos=val[0];
t_cmp.val[0]=1;t_cmp.val[1]=0;
if((*this)<obj) return (*this); // 小于除数直接返回本身
for(int i=pos;i>=1;i--){
t_cmp=t_cmp*10;
t_cmp.val[1]=val[i];
while(t_cmp>obj || t_cmp==obj) t_cmp=t_cmp-obj;
}
return t_cmp;
}
};
Ln f[505]={{1,1}};
int n;
void solve(){
f[1]=f[0];
for(int i=2;i<=n;i++){
f[i]=(f[i-1]*(4*i-2))/(i+1);
}
f[n].Lout();
}
int main(){
scanf("%d",&n);
solve();
return 0;
}