HDU 2067:うさぎの碁盤

うさぎの碁盤
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8905    Accepted Submission(s): 4631
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
   
   
   
   

 
Author
Rabbit
 
标题:このような方法:このテーマとカトラン数に似ているところがたくさんあることに気づいたことがありますか?そう、単一のカルトラン数で計算した結果、碁盤対角線側のルート個数で、すべてのルートを計算するには2を乗せればいいのです.うん!カトラン数は,組合せ数学において種々のカウント問題によく現れる数列である.
h(0)=1,h(1)=1,catalan数を繰返し式を満たす
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)
例えば、h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2
h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5
別のプッシュ
h(n)=h(n-1)*(4*n-2)/(n+1);
繰返し関係の解は次のとおりです.
h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
繰返し関係の別の解釈は、次のとおりです.
h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

void catalan() //     
{
    int i, j, len, carry, temp;
    a[1][0] = b[1] = 1;
    len = 1;
    for(i = 2; i <= 100; i++)
    {
        for(j = 0; j < len; j++) //  
            a[i][j] = a[i-1][j]*(4*(i-1)+2);
        carry = 0;
        for(j = 0; j < len; j++) //      
        {
            temp = a[i][j] + carry;
            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 = carry*10 + a[i][j];
            a[i][j] = temp/(i+1);
            carry = temp%(i+1);
        }
        while(!a[i][len-1]) //     
            len --;
        b[i] = len;
    }
}

#include <iostream>
#include <stdio.h>
using namespace std;
long long int a[40]= {1,1};
void solve()
{
    for(int n=2; n<37; n++)
        for(int i=0,j=n-1; i<n; i++,j--)
            a[n]+=a[i]*a[j];
}
int main()
{
    int n;
    solve();
    for(int i=1; cin>>n; i++)
    {
        if(n==-1)break;
        printf("%d %d %lld
",i,n,a[n]*2);
    }
    return 0;
}