[UVA] 10303 - How Many Trees ?

/*20141102 hanting*/
/*因為WA不知道錯哪，所以另外又寫了一個版本，
   後來發現存大數用10000會溢位，1000就AC了*/

/*遞迴+重載運算*/
#include <iostream>
#include <vector>
using namespace std;
struct BigNum
{
    vector<int> num;
    void operator+=(BigNum n)
    {
        int R=max(n.num.size(),num.size());
        num.resize(R+1);
        n.num.resize(R+1);
        vector<int> ans(1);
        for(int i=0;i<R;i++)
        {
            ans[i]+=num[i]+n.num[i];
            ans.push_back(ans[i]/1000);
            ans[i]%=1000;
        }
        if(!ans[R]) ans.pop_back();
        num=ans;
    }
    BigNum operator*(BigNum n)
    {
        BigNum ans;
        ans.num.resize(num.size()+n.num.size());
        for(int i=0;i<num.size();i++)
        {
            for(int j=0;j<n.num.size();j++)
            {
                ans.num[i+j]+=num[i]*n.num[j];
            }
        }
        for(int i=1;i<ans.num.size();i++)
        {
            ans.num[i]+=ans.num[i-1]/1000;
            ans.num[i-1]%=1000;
        }
        for(int i=ans.num.size()-1;i>0;i--)
        {
            if(ans.num[i]==0) ans.num.pop_back();
            else break;
        }
        return ans;
    }
    void operator*=(int n)
    {
        vector<int> ans(1);
        for(int i=0;i<num.size();i++)
        {
            ans[i]+=num[i]*2;
            ans.push_back(ans[i]/1000);
            ans[i]%=1000;
        }
        if(!ans[ans.size()-1]) ans.pop_back();
        num=ans;
    }
    friend ostream& operator<<(ostream& out, BigNum& n)
    {
        int first=n.num.size()-1;
        out<<n.num[first];
        for(int i=first-1;i>=0;i--)
        {
            if(n.num[i]<100) out<<0;
            if(n.num[i]<10) out<<0;
            out<<n.num[i];
        }
        return out;
    }
};
BigNum store[1005];
BigNum tree(int n)
{
    if(store[n].num.size()) return store[n];
    else
    {
        for(int i=0;i<n/2;i++)
        {
            store[n]+=tree(i)*tree(n-i-1);
        }
        store[n]*=2;
        if(n%2==1)store[n]+=tree(n/2)*tree(n/2);
        return store[n];
    }
}
int main()
{
    store[0].num.push_back(1);
    store[1].num.push_back(1);
    store[2].num.push_back(2);
    store[3].num.push_back(5);
    int N;
    while(cin>>N)
    {
        tree(N);
        cout<<store[N]<<endl;
    }
    return 0;
}

/*vector+函數*/
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int>,vector<int>);
vector<int> mul(vector<int>,vector<int>);
void output(vector<int>);
int main()
{
    int N;
    vector<int> num[1005];
    num[0].push_back(1);
    num[1].push_back(1);
    num[2].push_back(2);
    int MAX=2;
    while(cin>>N)
    {
        if(N<=MAX) output(num[N]);
        else
        {
            for(++MAX;MAX<=N;MAX++)
            {
                for(int i=0;i<MAX/2;i++)
                {
                    num[MAX]=add(num[MAX],mul(num[i],num[MAX-1-i]));
                }
                num[MAX]=mul(num[MAX],num[2]);
                if(MAX%2)
                {
                    num[MAX]=add(num[MAX],mul(num[MAX/2],num[MAX/2]));
                }
            }
            output(num[--MAX]);
        }
    }
    return 0;
}
vector<int> mul(vector<int> a,vector<int> b)
{
    vector<int> Result(a.size()+b.size());
    for(int i=0;i<a.size();i++)
    {
        for(int j=0;j<b.size();j++)
        {
            Result[i+j]+=a[i]*b[j];
        }
    }
    for(int i=1;i<Result.size();i++)
    {
        Result[i]+=Result[i-1]/1000;
        Result[i-1]%=1000;
    }
    for(int i=Result.size()-1;i>=0;i--)
    {
        if(!Result[i]) Result.pop_back();
        else break;
    }
    return Result;
}
vector<int> add(vector<int> a,vector<int> b)
{
    vector<int> Result;
    int Resize=max(a.size(),b.size());
    a.resize(Resize);
    b.resize(Resize);
    for(int i=0;i<a.size();i++)
    {
        Result.push_back(a[i]+b[i]);
    }
    Result.push_back(0);
    for(int i=1;i<Result.size();i++)
    {
        Result[i]+=Result[i-1]/1000;
        Result[i-1]%=1000;
    }
    if(!Result[Result.size()-1]) Result.pop_back();
    return Result;
}
void output(vector<int> N)
{
    for(int i=N.size()-1;i>=0;i--)
    {
        if(i!=N.size()-1&&N[i]<100) cout<<"0";
        if(i!=N.size()-1&&N[i]<10) cout<<"0";
        cout<<N[i];
    }
    cout<<endl;
}