卡特兰数的介绍

大家好，欢迎来到IT知识分享网。

一.定义

卡特兰数又称卡塔兰数，卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。但最早是欧拉在1753年解决凸包划分成三角形问题的时候，推出的Catalan数。

二.应用

1.括号化 ()() || (()) 

2.出栈次序(above)

3.凸多边形三角划分

4.给定结点组成二叉搜索树

5.n对括号正确匹配次数

三.例题

题目描述

有2n2n只小猫站成一圈，主人小明想把它们两两之间用绳子绑住尾巴连在一起。同时小明是个完美主义者，不容许看到有两根绳子交叉。请问小明有几种连线方案，可以把让所有小猫两两配对？

方案数很大，仅需输出方案数模（一个质数）的值。

输入格式

输入一个整数nn

输出格式

输出方案数对取模的值

输入输出样例

输入 #1

3

输出 #1

5

说明/提示

数据范围

AC代码

#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=2e5+5,maxs=2e5+2,mol=1e9+7; ll f[maxn],c[maxn],ans; ll qpow(ll a,ll x){ ll ans=1; while(x){ if(x&1)ans=ans*a%mol; a=a*a%mol; x>>=1; } return ans; } void Init(){ c[0]=1; for(int i=1;i<=maxs;i++)c[i]=c[i-1]*i%mol; } ll C(int n,int m){ return c[n]*qpow(c[m],mol-2)%mol*qpow(c[n-m],mol-2)%mol; } ll Catalan(int n){ return C(2*n,n)*qpow(n+1,mol-2)%mol; } int main(){ int n;cin>>n; Init(); cout<<Catalan(n); }