宇宙蘑菇 小m在宇宙中发现了一种奇怪的蘑菇,他每天都会固定分裂一次,长度为x的蘑菇回分裂成两个长度为x-1和x＋1的蘑菇

宇宙蘑菇
小m在宇宙中发现了一种奇怪的蘑菇,他每天都会固定分裂一次,长度为x的蘑菇回分裂成两个长度为x-1和x＋1的蘑菇,但长度为0的蘑菇是不存在的,所以长度为1的蘑菇只能生成长度为2的蘑菇.现在小m第一天有一个长度为2的蘑菇,他想知道第n天他有多少个蘑菇.
一道oi题,

是贴吧上的吧?
算法：f[n]:=f[n-1]*2-（1的个数）
先模拟一遍（见贴吧17楼,此处略）,1的个数为0 1 0 2 0 5 0 14 0 42 0 132.
而最大的值约等于2^10000,必须要用高精度!
如果为偶数,直接乘2,奇数要减1的个数,用ktl数组记录.
算ktl第n项,通项时间复杂度不够,找到如下算法：ktl[n]:=ktl[n-1]*2*(2*n-1)/(n+1);
源程序如下：
type A=array[0..10000] of longint;
var
b,c,x,an,ktl:A;
z:array[1..50000] of longint;
i,j,n,f,k:longint;
function divv(x:A;n:longint):A;
var i,j,h:longint; an:A;
begin
fillchar(an,sizeof(an),0);
j:=0;
for i:=x[0] downto 1 do
begin
an[i]:=(j*10+x[i]) div n;
j:=(j*10+x[i]) mod n;
end;
for i:=x[0] downto 1 do
if an[i]0 then begin an[0]:=i; break;end;
exit(an);
end;
function times(b:A;n:longint):A;
var ans:A;i:longint;
begin
fillchar(ans,sizeof(ans),0);
for i:=1 to b[0] do
begin
inc(ans[i],(b[i]*n) mod 10);
inc(ans[i+1],((b[i]*n) div 10) mod 10);
inc(ans[i+2],((b[i]*n) div 100) mod 10);
inc(ans[i+3],((b[i]*n) div 1000) mod 10);
inc(ans[i+1],ans[i] div 10);
ans[i]:=ans[i] mod 10;
end;
for i:=b[0] to b[0]+20 do
begin
inc(ans[i+1],ans[i] div 10);
ans[i]:=ans[i] mod 10;
end;
for i:= b[0]+20 downto b[0] do
if ans[i]0 then begin ans[0]:=i;break;end;
exit(ans);
end;
function decc(x:A):A;
var i,j:longint;
begin
for i:=1 to x[0] do
begin
x[i]:=x[i]-ktl[i];
if x[i]
再问： C++党路过……辛苦了……但是还是没有从数学的角度说明白为什么1的个数是卡塔兰数啊……求解释……
再答： 额。。。。。。我也不知道额。。。。规律就是这样么。。。。。 这串数就是卡塔兰数么。。。。。