卡特兰数

卡特兰数又称卡塔兰数（Catalan Number），是组合数学中一个经常出现在各种计数问题中的数列。

---

公式

　　1.递归公式1：

　　　　$f(n)=sum limits_{i=0}^{n-1}f(i) imes f(n-i-1)$

　　2.递归公式2：

　　　　$f(n)=frac{f(n-1) imes (4 imes n-2)}{n+1}$

　　3.组合公式1：

　　　　$f(n)=frac{C_{2n}^n}{n+1}$

　　4.组合公式2：

　　　　$f(n)=C_{2n}^n-C_{2n}^{n-1}$

---

代码实现

　　1.$n leqslant 35$

　　大了会爆long long

void Catalan()
{
	long long cat[36];
	cat[0]=cat[1]=1;
	for(int i=2;i<36;i++)
	{
		cat[i]=0;
		for(int j=0;j<i;j++)
			cat[i]=cat[i]+cat[j]*cat[i-j-1];
	}
}

　　2.$n>35$求$cat(n)mod p$，借助$Lucas$定理

　　$Lucas$定理$downarrow$

long long fac[N];
long long qpow(long long x,long long y,long long p)
{
	long long res=1;
	while(y)
	{
		if(y%2)res=(res*x)%p;
		y>>=1;
		x=(x*x)%p;
	}
	return res;
}
long long get_C(long long x,long long y,long long p)
{
	if(x<y)return 0;
	return fac[x]%p*qpow(fac[x-y]*fac[y]%p,p-2,p)%p;
}
long long lucas(long long x,long long y,long long p)
{
	if(!y)return 1;
	return (get_C(x%p,y%p,p)*lucas(x/p,y/p,p))%p;
}

　　3.利用高精计算卡特兰大数

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[100000],c[100000];
int mu[5001];
void mul(int p)
{
	int x=0,j;
	for(j=1;j<=a[0];j++)
	{
		a[j]=a[j]*p+x;
		x=a[j]/10;
		a[j]%=10;
	}
	a[j]=x;
	while(a[j]>9)
	{
		a[j+1]=a[j]/10;
		a[j]%=10;
		j++;
	}
	while(a[j]==0&&j>1)j--;
	a[0]=j;
}
void chu(int b)
{        
    int x=0,s=0,t=0;
    memset(c,0,sizeof(c));
    for(int i=1;i<=a[0];i++)
    {
        x=x*10+a[i];
        if(x/b!=0)s++;
        if(s==0)continue;
        c[++t]=x/b;
        x%=b;
    }
    for(int i=1;i<=t;i++)
    	a[i]=c[i];
    a[0]=t;
}     
int main()
{	
	a[0]=a[1]=1;
	scanf("%d",&n);
	for(int i=n+2;i<=2*n;i++)mul(i);
	reverse(a+1,a+a[0]+1);
	for(int i=2;i<=n;i++)chu(i);
	for(int i=1;i<=a[0];i++)printf("%d",a[i]);
}

---

做题经验

　　看见样例输入3，样例输出5，先想卡特兰数。