卡特兰数

卡特兰数是组合数学中，很经典的一类问题，一般可以解决一下问题

1. n个左括号和n个右括号组成的合法括号序列的数量为 Cat(n);
2. 1,2，3，……，n 经过一个栈，形成的合法出栈序列的数量为 Cat(n);
3. n 个节点构成的不同二叉树的数量为 Cat(n);
4. 在平面直角坐标系上，每一步只能向上走或向右走，从 (0,0) 走到 (n,n) 并且除两个端点外不接触直线 y = x的路线数量为 2Cat(n-1);
5. 给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的合法序列的个数

知道了这么多，那么卡特兰数应该怎么求呢？

Cat(n) = C(2n,n) / (n+1)

上面就是求卡特兰数的公式。

我们的问题就转化为了求组合数。

组合数可以直接用快速幂求分母和分子，再相除。

如以下问题：求C(n,r)的值，并对1e9+7取模。

见下列代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p=1e9+7;
ll n,r,res,fz,fm;
ll qmi(ll a,ll b)//快速幂a^b%p 
{
	ll re=1;
	while(b)
	{
		if(b&1)	re=(re*a)%p;
		b>>=1;
		a=(a*a)%p;
	}
	return re;
}
ll inv(ll a)//求a的逆元
{
	return qmi(a,p-2)%p;
} 
ll cnt(ll n,ll r)
{
	fz=fm=1;
	for(ll i=n;i>=n-r+1;i--)	fz=(fz*i)%p;
	for(ll i=1;i<=r;i++)	fm=(fm*i)%p;
	return (fz*inv(fm))%p;
}
int main()
{
	cin>>n>>r;
	cout<<cnt(n,r)<<endl;
	return 0;
}