1
#include<iostream>
2using namespace std;
3#define Max_N 100
4#define Max 60
5typedef struct bigint{
6 int data[Max];
7 int len;
8 friend bigint operator+(bigint,bigint);
9 friend bigint operator*(bigint,bigint);
10 void operator=(const bigint&y){
11 this->len=y.len;
12 for(int i=0;i<y.len;i++)
13 this->data[i]=y.data[i];
14 }
15}BIGINT;
16BIGINT Trees[Max_N+1];
17BIGINT operator+(BIGINT x,BIGINT y)
18{
19 BIGINT r;
20 int rlen=x.len>y.len?x.len:y.len;
21 int tmp,i,jinwei=0;
22 for(i=0;i<rlen;i++){
23 tmp=x.data[i]+y.data[i]+jinwei;
24 r.data[i]=tmp%10;
25 jinwei=tmp/10;}
26 if(jinwei)r.data[rlen++]=jinwei;
27 r.len=rlen;
28 return r;
29}
30void print(BIGINT x)
31{
32 for(int i=x.len-1;i>=0;i--)
33 printf("%d",x.data[i]);
34 printf("\n");
35}
36BIGINT operator*(BIGINT x,BIGINT y)
37{
38 BIGINT r;
39 int i,j;
40 memset(r.data,0,sizeof(r.data));
41 r.len=x.len+y.len;
42 for(i=0;i<x.len;i++)
43 for(j=0;j<y.len;j++)
44 r.data[i+j]+=x.data[i]*y.data[j];
45 for(i=0;i<r.len;i++){
46 r.data[i+1]+=r.data[i]/10;
47 r.data[i]%=10;}
48 while(r.data[i]){
49 r.data[i+1]+=r.data[i];
50 r.data[i]%=10;
51 i++;}
52 while(i>=0&&!r.data[i])i--;
53 r.len=i+1;
54 return r;
55}
56void init()
57{
58 int i,j;
59 memset(Trees,0,sizeof(Trees));
60 Trees[0].data[0]=1;
61 Trees[0].len=1;
62 for(i=1;i<=Max_N;i++)
63 for(j=0;j<i;j++)
64 Trees[i]=Trees[i]+Trees[j]*Trees[i-j-1];
65}
66int main()
67{
68 int n;
69 init();
70 while(scanf("%d",&n)!=EOF)
71 print(Trees[n]);
72 return 0;
73}
posted on 2008-03-02 17:10
zoyi 閱讀(212)
評(píng)論(2) 編輯 收藏 引用 所屬分類:
acm