[数论](8)组合数的应用:卡特兰数

卡特兰数:

卡特兰数(Catalan number)是 组合数学 中一个常出现在各种 计数问题 中的 数列

通项公式:

image-20210519020517868

例题:

image-20210519020537682

解法(来源acwing的番茄酱佬):

将 01 序列置于坐标系中,起点定于原点。若 0 表示向右走,1 表示向上走,那么任何前缀中 0 的个数不少于 1 的个数就转化为:路径上的任意一点,横坐标大于等于纵坐标。
题目所求即为这样的合法路径数量。
下图中,表示从 (0,0) 走到 (n,n) 的路径,在绿线及以下表示合法,若触碰红线即不合法。

image-20210519195925043

伪码:

因为数据极值是1e5,所以可以先预处理出来2n的阶乘和逆元阶乘,然后套用公式计算即可
(需要注意:公式必须整理为最简,若采用C(2n,n)-C(2n,n-2)),当n>66时,即会爆long long
需要用到:[ 快速幂模板,预处理阶乘模板 ]
套用公式:ans=fact[a]*infact[a-b]%p*infact[b]%p*qmi(n+1,p-2);

源码:

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define N 500010
const int p = 1e9+7;
LL fact[N],infact[N];
LL qmi(LL a,LL k){//快速幂模板
    LL res=1;
    while(k){
        if(k&1) res=res*a%p; 
        k>>=1;
        a=a*a%p;
    }
    return res;
}
void init(){//预处理阶乘
    fact[0]=infact[0]=1;
    for(int i=1;i<N;i++){
        fact[i]=i*fact[i-1]%p;
        infact[i]=infact[i-1]*qmi(i,p-2)%p;
    }
    return;
}
int main(){
    init();
    int n;
    scanf("%d",&n);
    int a=2*n,b=n;
    //卡特兰数
    LL ans=fact[a]*infact[a-b]%p*infact[b]%p*qmi(n+1,p-2);
    cout<<ans%p<<endl;
    return 0;
}

本文链接:

https://nullcode.fun/146.html
1 + 8 =
快来做第一个评论的人吧~