卡特兰数

2
3
-1

2
5

卡特兰数的计算，大数处理，包括大数乘和大数除的模拟；

#include<stdio.h>
#include<string.h>
int c[110][110],len[110];
void catalan(){
	int a[110][110],b[110][110];
	memset(a,0,sizeof(a)); 
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	c[1][0] = 1;
	int k;
	len[1] = 1; 
	for(int i = 2;i<=100;i++){
		int j,s=0;
		k=0;
		for(int j = 0;s!=0||j<len[i-1];j++){
			a[i][k++] = (c[i-1][j]*(4*i-2)+s)%10;
			s = (c[i-1][j]*(4*i-2)+s)/10;
		}
		int cha = 0,m=0;
		for(int jj = k-1; jj>=0;jj--){
			b[i][m++] = (a[i][jj] + cha *10) /(i+1);
			cha = (a[i][jj]+cha*10) % (i+1);
		}
		int mm = 0,ss;
		for( ss = 0;b[i][ss]==0;ss++);
	    for(int j=m-1;j>=ss;j--){
    		c[i][mm++] = b[i][j];
    	}
		len[i] = mm;
		}
	}
int main(){
	int n;
	catalan();
	while(scanf("%d",&n),n!=-1){
		for(int i = len[n]-1;i>=0;i--){
			printf("%d",c[n][i]);
		}
		printf("\n");
	}
}