Catalan Number入门

Catalan Number入门

九月 05, 2021

定义

这个cn啊，是组合数学里面经常会用到的东西，比如说：

  1. 让你算算二叉树的形态
  2. 又让你算算合法的括号序列
  3. 又或者让你算算出入栈的合法顺序
  4. 还可能让你去说说把多边形割成三角形方法

综上所述就是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的模板题
那么就是这样的了
贴代码(用的是第二个式子)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//洛谷的卡特兰数模板题 
#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\n",f[n]);
	return ;
}
int main(){
	int n;
	scanf("%d",&n);
	getcn(n);
	return 0; 
}

2.矩阵（洛谷P1722）

洛谷P1722
这一道题啊，可以看出来是一道卡特兰数的题，要求我们去模100，那么向第一个式子那样没有除法，只有加和乘的方法自然就是首选了，既然如此就用第一种方法写Cn就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//矩阵 洛谷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
这一道题啊，首先你这么考虑，任意选中其中一阶阶梯，然后呢就把整个阶梯分成了它上面的阶梯和它右面的阶梯。每一阶阶梯都这么去考虑，写出整个式子就会发现是卡特兰数了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
//洛谷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;
}

  1. 1. 定义
  2. 2. 于是有的人弄出来了它的式子
  3. 3. 例题
    1. 3.1. 1.栈（洛谷P1044）
    2. 3.2. 2.矩阵（洛谷P1722）
    3. 3.3. 3.树屋阶梯(洛谷P2532)