题解 P1044 【栈】

· · 题解

卡特兰数

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

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

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

公式一

递归公式

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;
}