pku2084 Game of Connections

http://poj.org/problem?id=2084
组合数学，Catalan数，高精度
  1 #include <stdio.h>
  2 #include <string>
  3 #include <iostream>
  4 
  5 using namespace std;
  6 
  7 const int ten[4] = {1, 10, 100, 1000};
  8 const int max1=1000;
  9 
 10 struct BigNumber{
 11     int d[max1];
 12     BigNumber(string s)
 13     {
 14         int len = s.size();
 15         d[0] = (len-1)/4+1;
 16         int i, j, k;
 17         for(i=1; i<max1; ++i) d[i] =0;
 18         for(i=len-1; i>=0; --i)
 19         {
 20             j = (len-i-1)/4+1;
 21             k = (len-i-1)%4;
 22             d[j]+=ten[k]*(s[i]-'0');
 23         }
 24         while(d[0]>1 && d[d[0]]==0) --d[0];
 25     }
 26     BigNumber()
 27     {
 28         *this = BigNumber(string("0"));
 29     }
 30     string toString()
 31     {
 32         string s("");
 33         int i, j, temp;
 34         for(i=3; i>=1; --i) if(d[d[0]]>=ten[i]) break;
 35         temp = d[d[0]];
 36         for(j=i; j>=0; --j)
 37         {
 38             s = s+(char)(temp/ten[j]+'0');
 39             temp %= ten[j];
 40         }
 41         for(i=d[0]-1; i>0; --i)
 42         {
 43             temp = d[i];
 44             for(j=3; j>=0; --j)
 45             {
 46                 s = s+(char)(temp/ten[j]+'0');
 47                 temp %= ten[j];
 48             }
 49         }
 50         return s;
 51     }
 52 }zero("0"), d, temp, mid1[15];
 53 
 54 BigNumber operator + (const BigNumber &a, const BigNumber &b){
 55     BigNumber c;
 56     c.d[0] = max(a.d[0], b.d[0]);
 57     int i, x=0;
 58     for(i=1; i<=c.d[0]; ++i)
 59     {
 60         x = a.d[i]+b.d[i] +x;
 61         c.d[i]=x%10000;
 62         x/=10000;
 63     }
 64     while(x!=0)
 65     {
 66         c.d[++c.d[0]] = x%10000;
 67         x/=10000;
 68     }
 69     return c;
 70 }
 71 
 72 BigNumber operator *(const BigNumber &a, const BigNumber &b){
 73     BigNumber c;
 74     c.d[0] = a.d[0] + b.d[0];
 75     int i, j, x;
 76     for(i=1; i<=a.d[0]; ++i)
 77     {
 78         x= 0;
 79         for(j=1; j<=b.d[0]; ++j)
 80         {
 81             x = a.d[i]*b.d[j]+x+c.d[i+j-1];
 82             c.d[i+j-1] = x%10000;
 83             x /= 10000;
 84         }
 85         c.d[i+b.d[0]] = x;
 86     }
 87     while((c.d[0]>1) && (c.d[c.d[0]]==0)) --c.d[0];
 88     return c;
 89 }
 90 
 91 int main()
 92 {
 93     BigNumber one("1"), h[103];
 94     int i, j, n;
 95     h[0] = one;
 96     h[1] = one;
 97     for(n=2; n<=100; n++)
 98     {
 99         BigNumber sum("0");
100         for(i=0; i<=n-1; i++)
101         {
102             sum = sum + (h[i] * h[n-i-1]);
103         }
104         h[n] = sum;
105     }
106     while(cin>>i, i+1)
107     {
108         cout<<h[i].toString()<<endl;
109     }
110     return 0;
111 }