catalan（卡特兰）数

一：

h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)h[0]=h[1]=1;

h(n)=(4n-2)/(n+1)*h(n-1)(n>1) h(0)=1

h(n)=C(2n,n)

一般情况（要取模）下的求法：

简单的catalan模板题

这个题要取1e9+7的模，直接按照公式h(n)=(4n-2)/(n+1)*h(n-1)(n>1) h(0)=1挨个递推求

除n+1变为乘n+1在1e9+7下的逆元

#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<set> #include<queue> #include<map> using namespace std; const int mod=1000000007; long long h[1000005]; long long rev(long long x) { long long ans=1,c=mod-2,base=x; x%=mod; while(c) { if(c&1) { ans*=base; ans%=mod; } base*=base; base%=mod; c/=2; } return ans; } int main() { long long n,i,t,T,cas=0; h[0]=1; for(i=1;i<=1000000;i++) { h[i]=(h[i-1]*(4*i-2))%mod; h[i]=(h[i]*rev(i+1))%mod; } scanf("%lld",&T); while(T--) { scanf("%lld",&n); printf("Case #%lld:\n%lld\n",++cas,h[n]); } return 0; }

二：递推求卡特兰数

假设ｋ为最后进栈的数，那么比ｋ小的数有ｋ－１个，比ｋ大的数有ｎ－ｋ个

这样总共会有（k-１）＊（ｎ－ｋ）种情况

ｋ可以取１......ｎ，所以卡特兰数有res[0]*res[n-1]+res[1]*res[n-2]+....+res[n-1]*res[0]个;

#include<iostream> #include<cstring> #include<cstdio> #include<set> #include<climits> using namespace std; typedef long long ll; ll res[60005]; int main() { ll n,i,j,t; res[0]=1; for(i=1;i<=60000;i++) { t=0; for(j=0;j<=i;j++) t+=res[j]*res[i-j-1]; //t等于 res[0]*res[i-1]+res[1]*res[i-2]+...res[i-1]*res[0] res[i]=t; } while(scanf("%lld",&n)==1) { printf("%lld\n",res[n]); } return 0; }