catalan（卡特兰）数

一h(n) h(0)*h(n-1) h(1)*h(n-2) ... h(n-1)h(0) (其中n2)h[0]h[1]1;h(n)(4n-2)/(n1)*h(n-1)(n1) h(0)1h(n)C(2n,n)一般情况要取模下的求法简单的catalan模板题这个题要取1e97的模直接按照公式h(n)(4n-2)/(n1)*h(n-1)(n1) h(0)1挨个递推求除n1变为乘n1在1e97下的逆元#includeiostream #includecstdlib #includecstring #includecstdio #includealgorithm #includecmath #includeset #includequeue #includemap using namespace std; const int mod1000000007; long long h[1000005]; long long rev(long long x) { long long ans1,cmod-2,basex; x%mod; while(c) { if(c1) { ans*base; ans%mod; } base*base; base%mod; c/2; } return ans; } int main() { long long n,i,t,T,cas0; h[0]1; for(i1;i1000000;i) { h[i](h[i-1]*(4*i-2))%mod; h[i](h[i]*rev(i1))%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]个;#includeiostream #includecstring #includecstdio #includeset #includeclimits using namespace std; typedef long long ll; ll res[60005]; int main() { ll n,i,j,t; res[0]1; for(i1;i60000;i) { t0; for(j0;ji;j) tres[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; }