仍然是数学
卡特兰数是一个非常神奇的东西
序列长这样↓
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786……(从第零项开始)
通常比较常用的应该是递推式和组合数的求法
递推式：
f(n)=f(n-1)*(4n-2)/(n+1)
其中令f(0)=1
组合数：
f(n)=C(2n,n)/(n+1)
通常情况下，碰到一道题，你不确定是不是卡特兰数，可以手动或写个暴力跑出来比对结果，一般来说前七八项符合条件，那就没什么问题了，反正我碰到的就是这个样子2333
我碰到过的卡特兰数题好像不是很多。吧
【一】二叉树
求n个节点构成的不同二叉树个数(n≤8000)
这是一道很经典的题目，很多地方都有，n的范围可以到七八千左右吧
最朴素的算法就是暴力搜索了，虽然拿不了几分==
把前面几个算出来，可以发现就是卡特兰数的序列，然后就可以直接写了
发现是卡特兰数不难，但是关键选择计算卡特兰数的方法
首先n那么大，显然是要高精度的，高精度的话复杂度就和答案长度有关了，n为七八千的时候，答案长度会达到四五千，是非常大的一个数，所以必须要考虑压位
递推式的话，时间复杂度为O(nlen)也就是递推复杂度乘上高精度乘除的复杂度
下面放上fp代码↓
const tt=1000000000; type arr=array[0..550]of int64; var n:longint; ans,ans1:arr; procedure init; var i:longint; begin assign(input,'secret.in');reset(input); assign(output,'secret.out');rewrite(output); readln(n); end; function mul(a:arr;x:longint):arr; var i:longint; c:arr; begin fillchar(c,sizeof(c),0); c[0]:=a[0]; for i:=1 to c[0] do begin inc(c[i],a[i]*x); inc(c[i+1],c[i] div tt); c[i]:=c[i] mod tt; end; if c[c[0]+1]>0 then inc(c[0]); while (c[0]>1)and(c[c[0]]=0) do dec(c[0]); exit(c); end; function divx(a:arr;x:longint):arr; var i:longint; c:arr; yu:int64; begin fillchar(c,sizeof(c),0); c[0]:=a[0];yu:=0; for i:=c[0] downto 1 do begin yu:=a[i] mod x; inc(a[i-1],yu*tt); c[i]:=a[i] div x; end; if c[c[0]+1]>0 then inc(c[0]); while (c[c[0]]=0)and(c[0]>1) do dec(c[0]); exit(c); end; procedure main; var i:longint; begin ans[0]:=1;ans[1]:=1; for i:=2 to n do ans:=divx(mul(ans,4*i-2),i+1); end; procedure print; var i,j:longint; s:string; begin write(ans[ans[0]]); for i:=ans[0]-1 downto 1 do begin str(ans[i],s); for j:=9 downto length(s)+1 do write(0); write(s); end; close(input);close(output); end; begin init; main; print; end.
如果选组合数的话，按照组合数定义一个个跑的话复杂度和递推差不多==
所以可以进行拆分质因子，因为任何一个合数都可以拆分成若干个质因子相乘的形式，质数看成它本身即↓
X=(p1^a1)*(p2^a2)*(p3^a3)*(p4^a4)*……*(pk^ak) (pi为质数)
所以通过枚举这些质因子求积，连乘的可以通过快速幂来实现，调用高精度乘法的次数减少了，只用在快速幂和幂的连乘，质因子只有根号个，复杂度就妥妥的降下来了，代码看下面↓
const tt=1000000000; type arr=array[0..550]of int64; var n:longint; hash:array[0..16005]of longint; vis:array[0..16005]of boolean; ans:arr; procedure init; begin assign(input,'secret.in');reset(input); assign(output,'secret.out');rewrite(output); readln(n); end; procedure maker; var i,j:longint; begin fillchar(vis,sizeof(vis),1); for i:=2 to trunc(sqrt(2*n)) do for j:=2 to 2*n div i do if vis[i] then vis[i*j]:=false; end; function count(x,p:longint):longint; begin count:=0; while x>=p do begin inc(count,x div p); x:=x div p; end; end; function mul(a,b:arr):arr; var i,j:longint; c:arr; begin fillchar(c,sizeof(c),0); c[0]:=a[0]+b[0]-1; for i:=1 to a[0] do for j:=1 to b[0] do begin inc(c[i+j-1],a[i]*b[j]); inc(c[i+j],c[i+j-1] div tt); c[i+j-1]:=c[i+j-1] mod tt; end; if c[c[0]+1]>0 then inc(c[0]); while (c[c[0]]=0)and(c[0]>1) do dec(c[0]); exit(c); end; function power(a,b:longint):arr; var sum,w:arr; begin w[0]:=1;w[1]:=a; sum[0]:=1;sum[1]:=1; while b<>0 do begin if b and 1=1 then sum:=mul(sum,w); w:=mul(w,w); b:=b>>1; end; exit(sum); end; procedure main; var i:longint; begin maker; fillchar(hash,sizeof(hash),0); for i:=2 to n*2 do if vis[i] then hash[i]:=count(n*2,i)-count(n,i)-count(n+1,i); ans[1]:=1;ans[0]:=1; for i:=2 to 2*n do if hash[i]<>0 then ans:=mul(ans,power(i,hash[i])); end; procedure print; var i,j:longint; s:string; begin write(ans[ans[0]]); for i:=ans[0]-1 downto 1 do begin str(ans[i],s); for j:=length(s)+1 to 9 do write(0); write(s); end; close(input);close(output); end; begin init; main; print; end.
所以就解好了
【二】出栈次序
一个栈(无穷大)的进栈序列为1，2，3，…，n，求不同的出栈序列个数
和上面那个题也是一个思路，最后答案序列是卡特兰数
类似的变形题有买票找零之类的
题目描述长这样↓
一场激烈的足球赛开始前，售票工作正在紧张的进行中，每张球票为 50 元，现有 2n 个人排队等待购票，其中有 n 个人手持 50 元的钞票，另外 n 个人手持 100 元的钞票，假设开始售票时售票处没有零钱，问 2n 个人有多少种排队方式，使售票处不至出现找不开钱的局面。
我最开始做的时候是找规律，发现答案刚好是卡特兰数就写了，后来发现可以转换成进出栈的问题就是50元看成进栈，100元的时候把找回的50元看做一次出栈就一毛一样了。。
【三】凸多边形的三角划分
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。求n多边形不同划分的方案数f(n)。
题目变形有在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数之类的
【四】括号化
矩阵连乘： P=A1*A2*A3*……*An，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，求不同括号化的方案数
方案数是f(n-1)，然而并没做过这类的题==
好像就没有其他什么东西了诶
【写的有漏洞的，欢迎路过大神吐槽】
2016-08-09 22:35:33
Ending.