卡特兰数 （Catalan）_卡特兰数公式

1.卡特兰数计算公式：

公式一：时间复杂度 O( n^2 )

递推式：h(0) = h(1) = 1                        (n >= 2)

               h(n) = h(0) * h (n -1) + h(1) * h(n - 2) +.....+ h(n - 1) * h(0)         

公式二：时间复杂度 O( n )

             (大数据时h(n)很大,取模时难保证不出现 h(n) % mod = 0)

               h(n) = h(n - 1) * (4 * n - 2) / (n + 1)  

公式三：时间复杂度 O( n )

组合数公式一：     h(n) = C(2n, n) / (n + 1)                (n = 0 , 1, 2.....)        //无法取模

公式四：时间复杂度 O( n )

组合数公式二：      h(n) = C(2n, n) - C(2n, n - 1)             (n = 0, 1, 2.....)        // 可以取模

公式四可以变成公式三：

 2.例题

1.球迷购票问题(球迷购票问题 - 洛谷)

题目背景

盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。

按售票处规定，每位购票者限购一张门票，且每张票售价为50元。在排成长龙的球迷中有N个人手持面值50元的钱币，另有N个人手持面值100元的钱币。假设售票处在开始售票时没有零钱。试问这2N个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。

题目描述

例如当n=2是，用A表示手持50元面值的球迷，用B表示手持100元钱的球迷。则最多可以得到以下两组不同的排队方式，使售票员不至于找不出钱。

第一种:A A B B

第二种:A B A B

[编程任务]

对于给定的n (0≤n≤20),计算2N个球迷有多少种排队方式，可以使售票处不至于找不出钱。

输入格式

一个整数，代表N的值

输出格式

一个整数，表示方案数

输入输出样例

输入 

2

输出 

2

说明/提示

必开QWORD

测试：N=15

回溯:1秒（超时）

模拟栈：大于10分钟

递归算法：1秒（超时）

动态规划：0 MS

组合算法：16 MS

AC代码：

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 30;
typedef unsigned long long ull;
ull f[N];
 
int main()
{
	int n;
	cin >> n;
	f[0] = f[1] = 1;
	for(int i = 2; i <= n; i++ )
	f[i] = f[i-1] * (4 * i - 2) / (i + 1);		//公式二
	cout << f[n] << endl;
	return 0;
}

2.栈（[NOIP2003 普及组] 栈 - 洛谷）

AC代码：

//法1 
#include <iostream>
#include <algorithm>
 
using namespace std;
 
long long f[40];
 
int main()
{
	int n;
	cin >> n;
	f[0] = f[1] = 1;
	for(int i = 2; i <= n; i++ )
		f[i] = f[i - 1] * (4 * i - 2) / (i + 1);		//公式二 
	cout << f[n] << endl;
	return 0;
}
#if 0 
//法2 
#include <iostream>
#include <algorithm>
 
using namespace std;
 
long long f[40];
 
int main()
{
	int n;
	cin >> n;
	f[0] = f[1] = 1;
	for(int i = 2; i <= n; i++ )
	{
		for(int j = 0; j < i; j++ )
			f[i] += f[j] * f[i - j - 1];		//递推式 
	}
	cout << f[n] << endl;
	return 0;
}
#endif 

3.火车进出栈问题（130. 火车进出栈问题 - AcWing题库）

一列火车 n 节车厢，依次编号为 1,2,3,…,n。

每节车厢有两种运动方式，进栈与出栈，问 n节车厢出栈的可能排列方式有多少种。

输入格式

输入一个整数 n，代表火车的车厢数。

输出格式

输出一个整数 s 表示 n 节车厢出栈的可能排列方式数量。

数据范围

1 ≤ n ≤ 60000

输入样例：

3

输出样例：

5

题解：由于n最大值为6 * 1e4,数据范围过大，使用python解决.

AC代码：

import math                #调用阶乘函数math.factorial()
 
a = int(input())            #输入转换为整型
 
print(math.factorial(2 * a) // math.factorial(a) // math.factorial(a) // (a+1))    #公式三

4.火车进栈（129. 火车进栈 - AcWing题库）

这里有 n 列火车将要进站再出站，但是，每列火车只有 1 节，那就是车头。

这 n列火车按 1 到 n 的顺序从东方左转进站，这个车站是南北方向的，它虽然无限长，只可惜是一个死胡同，而且站台只有一条股道，火车只能倒着从西方出去，而且每列火车必须进站，先进后出。

也就是说这个火车站其实就相当于一个栈，每次可以让右侧头火车进栈，或者让栈顶火车出站。

车站示意如图：

            出站<——    <——进站
                     |车|
                     |站|
                     |__|

现在请你按《字典序》输出前 20 种可能的出栈方案。

输入格式

输入一个整数 n，代表火车数量。

输出格式

按照《字典序》输出前 20 种答案，每行一种，不要空格。

数据范围

1≤n≤20

输入样例：

3

输出样例：

123
132
213
231
321

AC代码：

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
 
using namespace std;
 
vector<int> v;			//出栈序列 
stack<int> s;			//栈 
int ans = 20, sum = 1;		//ans方案数
int n;
 
void dfs()
{
	if (!ans)		//20种方案 
	return ;
	if (v.size() == n)
	{
		ans--;
		for( auto x : v)			//输出v中元素 
		cout << x;
		cout << endl;
		return ;
	}
	
	if (!s.empty())					//出栈 
	{
		v.push_back(s.top());
		s.pop();
		dfs();
		s.push(v.back());			//状态还原 
		v.pop_back();
	}
	
	if(sum <= n)				//进栈 
	{
		s.push(sum);
		sum ++;
		dfs();
		sum --;			//状态还原 
		s.pop();
	}
}
 
int main() 
{
	cin >> n;
	dfs();
	return 0; 
}