浅谈卡特兰数

参考学姐的博客：http://www.cnblogs.com/yuelian/p/8719175.html

以下摘自百度百科

卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名，其前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

卡特兰数Cn满足以下递推关系：

令h(0)=1,h(1)=1，catalan数满足递推式：

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

　　例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2

　　h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5

另类递推式：

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

递推关系的解为：

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

递推关系的另类解为：

　　h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

卡特兰数的求解方法：

　　　　1.最基本的n^2递推例题：洛谷 P1044

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int f[20];
int main() {
    scanf("%d", &n);
    f[0] = 1;
    f[1] = 1, f[2] = 2;
    for(int i = 3; i <= n; ++i)
        for(int j = 0; j < i; ++j)
        f[i] += f[j]*f[i-j-1];
    cout<<f[n]<<'
';    //据说有人做过实验cout在只输出数字时比printf快，但如果加上换行“endl”就会慢很多
    return 0;
}

数据范围较小，直接 n^2

　　　　2.卡特兰数的第n项h(n)=C(2n,n)-C(2n,n-1),所以用求组合数的方法求卡特兰数即可，针对对一个大质数取模的代码

#include<iostream>
#include<cstdio> 
using namespace std;
int n,p;
int js[100005];
int prime[100005];
bool vis[100005];
int cnt[100005];
int qpow(int a,int b) {    //快速幂求逆元 
    int ans = 1;
    while(b) {
        if(b&1) ans = (1ll*a*ans)%p;
        a = (1ll*a*a)%p;
        b>>=1;
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &p);//求第n项，对p取模的结果，p为大质数
    js[0] = 1;
    for(int i=1;i<=2*n;++i)
        js[i] = (1ll*js[i-1]*i)%p;
    int a = qpow(1ll*js[n]*js[n]%p,p-2), b = qpow(1ll*js[n-1]*js[n+1]%p,p-2);
    a = 1ll*a*js[2*n]%p, b = 1ll*b*js[2*n]%p;
    int ans = (a-b+p)%p; //a = C(2n,n)%p, b = C(2n,n-1)%p 
    printf("%d", ans);
    return 0;
}

View Code

　　　　3.我们可以由第一种求法看出来卡特兰数增长的是很快的，所以当要求的项数比较大而且不能取模时，需要用到高精，这时分解质因数求卡特兰数就是一个很好的方法。

例题：洛谷 P2532

#include<iostream>
#include<cstdio>
using namespace std;
int n; 
int prime[1500],cnt;
bool vis[1550];
int tong[1050];
int ans[1100],len;
void cheng(int x,int sum) {    //高精乘低精
    while(sum--) {
        for(int i=1;i<=len;++i)ans[i]*=x;
        for(int i=1;i<=len;++i)
            if(ans[i]>9) {
                ans[i+1] += ans[i]/10, ans[i]%=10;
                if(i+1>len) len++;
            }
    }
}
int main()
{
    scanf("%d", &n);
    vis[0] = vis[1] = 1;
    for(int i=2;i<=2*n;++i) {    //分解质因数
        if(!vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=2*n;++j) {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
    for(int i=1;i<=cnt;++i)
    {
        int tmp=2*n;
        while(tmp/prime[i]>0) tong[i] += tmp/prime[i], tmp /= prime[i];
        tmp = n; while(tmp/prime[i]>0) tong[i]-=tmp/prime[i], tmp /= prime[i];
        tmp = n+1; while(tmp/prime[i]>0) tong[i]-=tmp/prime[i], tmp /= prime[i]; 
    }
    ans[1]=1, len=1;
    for(int i=1;i<=cnt;++i)
        if(tong[i]) cheng(prime[i], tong[i]);
    for(int i=len;i>=1;i--) printf("%d",ans[i]);
    return 0;
}

View Code

　　　　4.卡特兰数的递推公式h(n)=h(n-1)*(4*n-2)/(n+1),看起来好像挺简单的样子，不过从来没有用过这个递推式无奈