卡特兰数

卡特兰数

首先，我们设f（n）=序列个数为n的出栈序列种数。（我们假定，最后出栈的元素为k，显然，k取不同值时的情况是相互独立的，也就是求出每种k最后出栈的情况数后可用加法原则，由于k最后出栈，因此，在k入栈之前，比k小的值均出栈，此处情况有f(k-1)种，而之后比k大的值入栈，且都在k之前出栈，因此有f(n-k)种方式，由于比k小和比k大的值入栈出栈情况是相互独立的，此处可用乘法原则，f(n-k)*f(k-1)种，求和便是Catalan递归式。看到大家的题解都写到了卡特兰数，但是没有细细的讲讲这跟本题有什么关系本题的描述十分简单。n个数依次进栈，可随机出栈。求有几种可能。

dfs可以解，但是递推仿佛好像如同看上去貌似更简单一些。

解释一下原理：建立数组f。f[i]表示i个数的全部可能性。f[0] = 1, f[1] = 1; //当然只有一个设 x 为当前出栈序列的最后一个，则x有n种取值由于x是最后一个出栈的，所以可以将已经出栈的数分成两部分 1. 比x小 2. 比x大

比x小的数有x-1个，所以这些数的全部出栈可能为f[x-1]

比x大的数有n-x个，所以这些数的全部出栈可能为f[n-x]

这两部分互相影响，所以一个x的取值能够得到的所有可能性为f[x-1] * f[n-x]

另外，由于x有n个取值，所以

ans = f[0] * f[n-1] + f[1] * f[n-2] + … + f[n-1] * f[0];

这，就是传说中的卡特兰数附上代码：

#include <cstdio>
int n, f[30];
int main()
{
    //递推实现卡特兰数
    scanf("%d", &n);
    f[0] = 1, 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]; //递推公式    //f(2)=f(0)*f(1)+f(1)*f(0);
    printf("%d", f[n]);
    return 0;
}

卡特兰数

这是一道经典的卡特兰数例题

卡特兰数有四个公式，显然这题数据太水都可过，但我们要分析每个公式的用处。

以下内容神犇请无视（话说神犇也不会看这种水题的题解）

公式一

递归公式

h(0)=h(1)=1

h(n)= h(0) * h(n-1)+h(1) * h(n-2) + … + h(n-1) * h(0) (n>=2)

如果我们用这个公式显然我们要使用递归算法，那么数据一大就在时空上很麻烦

公式二

递推公式

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

这个公式应用递推，看上起十分和善

但对大数据呢？

我们注意到大数据的时候h(n)会很大，这时候题目一般会让你对某素数取模（当然你可以打高精度（划掉））

但你在取模过程中难保一个 h(n) % mod = 0

那么根据公式下面所有的数都会等于0，于是你就愉快的WA了

公式三

组合数公式1

h(n) = C(2n,n) / (n+1) (n=0,1,2,…)

卡特兰数可以与组合数联系起来，得到上面的公式

而组合数就是一个杨辉三角，可以递推得到（这个不属于这道题的讨论范围我假装你们都会（逃））

但我们发现对于大数据你要取模，而对于除法你是没办法用膜的性质的（当然你可以应用逆元（划掉）），所以造成了麻烦

公式四

组合数公式2

h(n) = c(2n,n) – c(2n,n-1) (n=0,1,2,…)

与组合数公式1不同这个是两个组合数的减法

减法是可以用膜的性质的，于是你可以愉快的AC了。

所以我写了这么多就是想说，对于一个特定的任务，可能会有很多方法求解，但其实只要稍稍分析一下就会发现有一种方法是通用而优美的，我在没认真思考前都是记的四个公式，但是有一天我真的认真想过后才发现其实我就记住公式四就好了。

所以学习啊，还是要学会认真思（tou）考（lan）:

#include<cstdio>
#define siz 20
using namespace std;
​
int n;
int c[siz*2][siz];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=2*n;i++) c[i][1]=c[i][i]=1;
    for(int i=3;i<=2*n;i++)
    for(int j=2;j<i;j++)
    c[i][j]=c[i-1][j]+c[i-1][j-1];
    printf("%d",c[2*n][n]-c[2*n][n-1]);
    return 0;
}