***************************************转载请注明出处：http://blog.csdn.net/lttree***************************************

Train Problem II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5589    Accepted Submission(s): 3022

12310

12516796
Hint
The result will be very large, so you may not process it by 32-bit integers.

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1023

 这道题就是出栈的种类数，典型的卡特兰数问题，如果参加过第五届蓝桥杯，C/C++ B组题目中，也有同样的问题，

但是是一个结果填空，求16个火车时的种类数。

当时，不会卡特兰数，用递归模拟来推出来的。

这次就要用卡特兰数了，这道题还要考虑大数相乘，Hint也提示了，会超过的，100的卡特兰数就有58位数字，

longlong当然也没法达到了。

对于大数卡特兰数，百度百科直接就有样例程序，照样子复制粘贴直接搞定。

如果，你足够耐心，想另类点，你也可以打表：

可以去戳这个网站，里面有1到100的卡特兰数 http://blog.csdn.net/lttree/article/details/29392541

小伙伴们，是不是惊呆了？！

我的做法就是用之前大数乘法的理念，每个数组存5位数。

这样做有几点要注意：

1.先乘起来，存到数组，再除。

2.除的时候，要将前一位的余数*相应位数（我存5位，所以乘以 100000 ） 加上当前数组内容再算除法。

3.最后要看高位是否为0

4.最后输出的时候，还要补0，就比如第12个卡特兰数 208012，存在数组肯定是 8012,2 

如果输出的时候没有补0，则会输出28012，显然是错误的。这个可以用填充来解决，C语言的printf比较简便。

恩，这道题，卡了一段时间，关键是忘了先算乘最后算除。

/****************************************************************************************           Author:Tree                    **    From :  blog.csdn.net/lttree          **      Title : Train Prob                  **    Source: hdu 1023                      **      Hint :  卡特兰数                    ****************************************************************************************/// h(n)=h(n-1)*(4*n-2)/(n+1)#include <stdio.h>// 100的卡特兰数有58位，所以(60/5)+1=13 ,不可以是12哟int cata[101][13];void make_catalan( void ){	int i,j,jw,temp1,temp2;	cata[1][0]=cata[1][1]=1;	for( i=2;i<=100;++i )	{	    // 乘法		cata[i][0]=cata[i-1][0];		temp1=4*i-2;		jw=0;		for( j=1;j<=cata[i][0];++j )		{			cata[i][j]=( cata[i-1][j]*temp1 +jw )%100000;			jw=( cata[i-1][j]*temp1 + jw )/100000;		}		if( jw!=0 )		{			cata[i][j]=jw;			++cata[i][0];		}		// 除法		temp1=temp2=0;		for( j=cata[i][0];j>=1;--j )        {            temp2=(cata[i][j]+temp1*100000)%(i+1);            cata[i][j]= (cata[i][j]+temp1*100000) / (i+1) ;            temp1=temp2;        }        // 处理高位0        if( !cata[i][ cata[i][0] ] )            --cata[i][0];	}}int main(){	int i,n;	make_catalan();	while( ~scanf("%d",&n) )	{        printf("%d",cata[n][ cata[n][0] ]);        // 注意非最高位要补0		for( i=cata[n][0]-1;i>=1;--i )            printf("%05d",cata[n][i]);        printf("\n");  }	return 0;}