大整数
#include<stdio.h>
int a[200][1000]={0};
int main()
{
int i,j,k,len,t,n;
a[1][0]=1;len=1;
for(i=2;i<=100;i++)
{
for(j=0;j<len;j++)
a[i][j]=a[i-1][j]*(4*i-2)*i;
for(k=j=0;j<len;j++)
{
a[i][j]+=k;
k=a[i][j]/10000;
a[i][j]%=10000;
}
while(k)
{
a[i][len++]=k%10000;
k=k/10000;
}
for(j=len-1;j>=0;j--)
{
t=a[i][j]%(i+1);
a[i][j-1]+=t*10000;
a[i][j]=a[i][j]/(i+1);
}
}
while(scanf("%d",&n),n!=0)
{
for(i=len-1;i>=0;i--)
if(a[n][i]!=0)
{
printf("%d",a[n][i]);
break;
}
for(j=i-1;j>=0;j--)
printf("%04d",a[n][j]);
printf("\n");
}
return 0;
}
此題基本上和1130的 How Many Trees?类似,只是多加了一个排列数。
卡特兰数的公式C(n) = ( 4n - 2 ) * C( n-1) / (n+1)
这个相当于在卡特兰数的基础上乘以一个n!,即:
n!*C(n) = n! * (4n - 2) * C(n-1) / (n+1) = (4n - 2) * n * ((n-1)! * C(n-1)) / (n+1)
另H(n) = n! * C(n),则有: H(n) = (4n - 2) * n * H(n-1) / (n+1)
H(1) = 1*C(1) = 1
所以推导公式如下:
H(1) = 1;
H(n) = n * (4n - 2) * H(n-1) / (n+1)