卡特兰数
- 定义
卡特兰数非常常见，最为典型的就是给定n个1和n个0排列成为一个2n长度的01序列，要求对于任一个\(1\le k\le 2n\)都有从第一个数到第k个数中0的个数都不少于1的个数。
- 求法及其推导
我们可以把这个01序列抽象成一个具体的问题:
0代表向右走一步，1代表向上走一步，要求一共向右走n步向上走n步对于任一时刻向右走的步数都大于向上走的步数，最终到达(n,n)。
我们不难发现y=x是一个分界点，如果走的路线全部都在y=x(图中绿线）的下方或者只是碰到y=x并未越过它则符合条件，当且仅当路线与y=x+1(图中红线)有交点不符合条件。
设不符合条件的路径与红线的第一个交点为t，
这里有一系列逻辑推导关系:\(一个路径是不合法路径\Longrightarrow 它与红线有一个交点t\Longrightarrow 这条路径t点之后的步数里向右走要比向上走多一步\Longrightarrow将t之后的路径沿着红线翻转后向上走要比向右走多两步\Longrightarrow 翻转后一定到达(n-1,n+1)点\),因为到达(n-1,n+1)点一定会穿过红线那么就有：所有非法路径的条数等于到(n-1,n+1)的条数。即为：\(C_{2n}^{n}-C_{2n}^{n-1}=\frac{(2n)!}{n!n!}-\frac{(2n)!}{(n-1)!(n+1)}=\frac{(2n)!(n+1)}{(n+1)!n!}-\frac{(2n)!n}{n!(n+1)!}=\frac{2n!}{(n+1)!n!}=\frac{1}{n+1}*\frac{2n!}{n!n!}=\frac{1}{n+1}C_{2n}^{n}\),所以卡特兰数为:\(\frac{C_{2n}^{n}}{n+1}\)
-代码实现
给定n个0和n个1，求卡特兰数，结果模上\(10{^9}+7\)
#include<iostream>
using namespace std;
typedef long long LL;
const int N=2e5+10;
const int mod=1e9+7;
int fact[N],infact[N];
int qmi(int a,int b,int p)
{
int res=1;
while(b)
{
if(b&1)
{
res=(LL)res*a%p;
}
b>>=1;
a=(LL)a*a%p;
}
return res;
}
int main()
{
int n;
cin>>n;
int a=2*n,b=n;
fact[0]=infact[0]=1;
for(int i=1;i<=a;i++)
{
fact[i]=(LL)fact[i-1]*i%mod;
infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;
}
int res=(LL)fact[a]*infact[b]%mod*infact[b]%mod*qmi(n+1,mod-2,mod)%mod;
printf("%d",res);
return 0;
}