HDoj 2067ウサギの碁盤【catalan数列変形】

うさぎの碁盤
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7404    Accepted Submission(s): 3931
Problem Description
ウサギのおじさんは外から旅行から帰ってきてプレゼントを持ってきて、ウサギは喜んで自分の部屋に帰って、開けてみると碁盤で、ウサギはがっかりしました.しかし、数日もしないうちに碁盤の面白さを発見しました.起点(0,0)から終点(n,n)までの最短経路数はC(2 n,n)で、今ウサギはまた対角線(ただし対角線上の格子点に触れることができる)を通り抜けなければ、このような経路数はいくらあると思いますか?ウサギは長い間考えていたが、今はウサギにこの問題を解決してもらいたいと思っています.あなたにとって難しくないでしょう.
Input
1個の数n(1<=n<=35)を入力する毎に、nが−1に等しいときに入力を終了する.
Output
各入力データ出力パス数について、具体的なフォーマットはSampleを参照してください.
Sample Input

   
   
   
   

    
    
    
    1
3
12
-1
   
   
   
   

Sample Output

   
   
   
   

    
    
    
    1 1 2
2 3 10
3 12 416024
   
   
   
   

 
catalan数列の各数に2を乗算します.
 

#include<stdio.h>
#include<string.h>
int a[40][500];
int b[40];//    
void catalan()
{
    int i,j;
    int len;
    int carry,temp;
    a[1][0]=b[1]=len=1;
    for(i=2;i<=35;i++)
    {
        for(j=0;j<len;j++)
        {
            a[i][j]=a[i-1][j]*(4*i-2);
        }
        carry=0;
        for(j=0;j<len;j++)
        {
            temp=carry+a[i][j];
            a[i][j]=temp%10;
            carry=temp/10;
        }
        while(carry)//   
        {
            a[i][len++]=carry%10;
            carry/=10;
        }
        carry=0;
        for(j=len-1;j>=0;j--)
        {
            temp=a[i][j]+carry*10;
            a[i][j]=temp/(i+1);
            carry=temp%(i+1);
        }
        while(!a[i][len-1])//      
        len--;
        b[i]=len;
    }
}
void Catalan()
{
    int i,j;
    int carry,temp,len;
    for(i=1;i<=35;i++)
    {
        len=b[i];
        carry=0;
        for(j=0;j<len;j++)
        {
            temp=a[i][j]*2+carry;
            carry=temp/10;
            a[i][j]=temp%10;
        }
        while(carry)
        {
            a[i][len++]=carry%10;
            carry/=10;
        }
        b[i]=len;
    }
} 
int main()
{
    int n,i,j=1;
    catalan();//      
    Catalan();//         2 
    while(scanf("%d",&n)!=EOF)
    {
        if(n==-1)
        break;
        printf("%d %d ",j++,n);
        for(i=b[n]-1;i>=0;i--)
        printf("%d",a[n][i]);
        printf("
");
    }
    return 0;
}