hdu 1023 Train Problem II(カーターランド数の応用)スタックの統計

http://baike.baidu.com/view/2499752.htmカトラン数の応用.
http://acm.hdu.edu.cn/showproblem.php?pid=1023
数式:
令h(1)＝1、h(2)＝2、catalan数は再帰式を満足する:
 
h(n)＝h(1)＊h(n−1)＋h(2)＊h(n−2)＋…h(n−1)h(1)(n＞＝3)
 
例えば、h(3)=h(1)*h(2)+h(2)*h(1)=1*1+1*1=2
 
h(4)=h(1)*h(3)+h(2)*h(2)+h(3)*h(1)=1*2+1*1+2*1=5
 
別の再帰式:
 
h(n)=h(n-1)*(4*n-2)/(n+1)
 
デリバリー関係の解は次の通りです.
 
h(n)=C(2 n,n)/(n+1)(n=1,2,3,…)
ここで私が使っていたデリバリー関係式を始めたばかりですが、データが大きすぎて、オフラインです.もとはまだ大きい数の処理を試験しなければなりませんでした.だから再帰式を使います.
これは期末試験が終わった後の第一の問題です.長い間問題をしていません.ちょっと疎遠になりました.思考も怠惰になりました.自分をリラックスして遊びに行きたいですが、自分の心の中の夢を忘れられません.頑張って!同前スター


View Code

#include <iostream>
#include <cstdio>
using namespace std;
int a[105][105],b[105];//b        ，a    
int main(){
    int i,j,len,tmp,r,n;
    a[1][0]=1;
    b[1]=1;
    len=1;
    for(i=2;i<105;i++){
      for(j=0;j<len;j++){//    
        a[i][j]=a[i-1][j]*(4*i-2);
      }
      for(j=r=0;j<len;j++){//     
         tmp=a[i][j]+r;
         a[i][j]=tmp%10;
         r=tmp/10;
      }
      while(r){//     
        a[i][len++]=r%10;
        r=r/10;
      }
      for(j=len-1;j>=0;j--){//    
          tmp=a[i][j]+r*10;
         a[i][j]=tmp/(i+1);
         r=tmp%(i+1);
      }
      while(a[i][len-1]==0){//  0   
         len--;
      }
      b[i]=len;
    }
      while(scanf("%d",&n)!=EOF){
      for(i=b[n]-1;i>=0;i--)
      cout<<a[n][i];
      cout<<endl;
    }
    return 0;
}