//高精度最終較完美解[url]http://acm.zjnu.cn/show.asp?tab=arithmetic&id=67[/url]
//done by smallrain . 05,4,7

#include<iostream>
#include<fstream>
#include<string>
#include"time.h"
using namespace std;


struct cresi                                    //此結(jié)構(gòu)體用來(lái)存余數(shù),并打印
{
    int *p_resi;                                //指向內(nèi)存中存放余數(shù)的連續(xù)空間
    int len_resi;                                //余數(shù)存放空間的長(zhǎng)度
    void print()                                //打印余數(shù)
    {
        for(int i=len_resi-1;i>=0;i--)
        {
            cout<<p_resi[i];
        }
        cout<<endl;
    }
};///:p

struct cresi resi;                              //定義結(jié)構(gòu)體全局變量,用于處理高精度整數(shù)除法的余數(shù)
    
class cata                                      //定義高精度類,可實(shí)現(xiàn)任意大數(shù)的四則運(yùn)算
{
public:

    cata(int Max=10);
    ~cata();
    bool empty() const;

    int length() const;                          //存放高精度數(shù)的數(shù)組的長(zhǎng)度

    void printcata(ofstream &out) const;
    void pricata();                              //打印高精度數(shù)
    void del_first();                            //刪除高精度數(shù)組的首單元

    cata &getdata(const string &x);              //由于數(shù)據(jù)讀入用的是string,把字符串轉(zhuǎn)化為整形數(shù)組,并且完成逆置

    cata &operator +(const cata &y);            //實(shí)現(xiàn)高精度的加法,結(jié)果存放于被加數(shù)中,且返回被加數(shù)對(duì)象的指針
    cata &operator -(const cata &y);            //實(shí)現(xiàn)高精度的減法,結(jié)果存放于被減數(shù)中,且返回被減數(shù)對(duì)象的指針
    cata &operator *(const cata &y);            //實(shí)現(xiàn)高精度的乘法,結(jié)果存放于被乘數(shù)中,且返回被乘數(shù)對(duì)象的指針
    cata &operator /(const cata &y);            //實(shí)現(xiàn)高精度的除法,結(jié)果存放于被除數(shù)中,且返回被除數(shù)對(duì)象的指針
    cata &operator =(const cata &y);            //重載賦值運(yùn)算符,用以實(shí)現(xiàn)cata對(duì)象的賦值

    friend bool dispose_boundary(const cata &m,const cata &n);        //處理邊界情況
    friend int compare_cata(const cata &x,const cata &y);            //比較兩個(gè)高精度數(shù)的大小
    friend void result(cata &m,cata &n,cata &result_combination,cata &result_catalan); //產(chǎn)生大組合數(shù)結(jié)果和catalan數(shù)結(jié)果
    friend void boundary_result(cata &m,cata &result_combination,cata &result_catalan); //在邊界條件下產(chǎn)生上述結(jié)果

private:
    int n;                                      //存放高精度數(shù)的數(shù)組的長(zhǎng)度
    int displacement;                            //數(shù)組偏移量,用于除法移位
    int MaxSize;
    int *data;                                  //用于申請(qǐng)動(dòng)態(tài)空間,指向存放高精度數(shù)的數(shù)組
};///:p

inline cata::cata(int Max)                      //構(gòu)造函數(shù)
{
    MaxSize=Max;
    data=new int[MaxSize];
    n=0;
    displacement=0;
}///:p

inline cata::~cata()                            //析構(gòu)函數(shù)
{
    delete [] data;
}///:p

inline bool cata::empty() const                  //判斷是否非空,在本程序中無(wú)用
{
    return n==0;
}///:p

inline bool dispose_boundary(const cata &m,const cata &n)
{
    if(((1==n.n)&&(n.data[0]==0))||compare_cata(m,n)==2)
    {
        return false;
    }
    else
    {
        return true;
    }
}///:p

inline int cata::length() const                  //返回高精度數(shù)的長(zhǎng)度,即是數(shù)組長(zhǎng)度
{
    return n;
}///:p

inline void cata::del_first()                    //刪除存放高精度數(shù)的數(shù)組的首單元,在除法中運(yùn)用
{
    /*for(int i=1;i<n;i++)
    {
        data[i-1]=data[i];
    }*/
    displacement+=1;
    n-=1;
}///:p

void cata::pricata()                            //打印高精度數(shù)到控制臺(tái)
{
    for(int i=n-1;i>=0;i--)
    {
        cout<<data[i];
    }
    cout<<endl;
}///:p

cata &cata::getdata(const string &str)          
{
    int len_int=str.length(),len_str=len_int;    
    if(this->n!=len_int)
    {
        delete [] data;
        data=new int [len_int];
        if(NULL==data)
        {
            cout<<"the error take place in getdata()"<<endl;
            exit(1);
        }
    }
    for(int j=0;j<len_int;j++)                  //完成string到int型數(shù)組的轉(zhuǎn)換,并且逆置
    {
        data[j]=(int)(str[len_str-1-j]-48);
    }
    n=len_int;
    return *this;
}///:p

cata &cata::operator +(const cata &y)
{
    int len_x=length(),len_y=y.length();
    int len_max=len_x>len_y? len_x:len_y,len_min=len_x<len_y? len_x:len_y;
    int *result=new int[len_max+1];            //result存放高精度加法結(jié)果
    for(int i=0;i<len_max+1;i++)                //將result全部置0
    {
        result[i]=0;
    }
    int carry=0,temp_1,temp_2;                  //carry為進(jìn)位
    for(i=0;i<len_min;i++)                      //按位加,分兩步做
    {
        temp_2=temp_1=data[i]+y.data[i]+carry;
        carry=temp_1/10;
        if(carry)
            result[i]=temp_2%10;
        else result[i]=temp_2;
    }
    if(len_x>=len_y)
    {
        for(i=len_min;i<len_max;i++)
        {
            temp_2=temp_1=data[i]+result[i]+carry;
            carry=temp_1/10;
            if(carry)
            {
                result[i]=temp_2%10;
            }
            else 
            {
                result[i]=temp_2;
            }
        }
    }
    else
    {
        for(i=len_min;i<len_max;i++)
        {
            temp_2=temp_1=y.data[i]+result[i]+carry;
            carry=temp_1/10;
            if(carry)
            {
                result[i]=temp_2%10;
            }
            else 
            {
                result[i]=temp_2;
            }
        }
    }
    if(carry)
    {
        result[len_max]=carry;
        n=len_max+1;
    }
    else
    {
        n=len_max;
    }
    int *temp=result;                            //指針的交換
    result=data;                                
    data=temp;
    delete [] result;
    return *this;
}///:p

cata &cata::operator -(const cata &y)
{
    int len_max=length(),len_y=y.length();
    int *result=new int [len_max];              //result用于存放高精度減法的結(jié)果
    if(NULL==result)
    {
        cout<<"the error take place in -"<<endl;
        exit(1);
    }
    for(int i=0;i<len_max;i++)
    {
        result[i]=0;
    }
    int borrow=0,temp;                            //borrow位借
    int displace=y.displacement;
    for(i=0;i<len_y;i++)                        //按位減,分兩步做
    {
        temp=data[i]+10-y.data[i+displace]-borrow;
        if(temp>=10)
        {
            temp=temp-10;
            borrow=0;
        }
        else
        {
            borrow=1;
        }
        result[i]=temp;
    }
    for(int j=len_y;j<len_max;j++)
    {
        temp=data[j]+10-result[j]-borrow;
        if(temp>=10)
        {
            temp=temp-10;
            borrow=0;
        }
        else
        {
            borrow=1;
        }
        result[j]=temp;
    }
    n=len_max;
    i=1;
    while(result[n-i]==0&&i<n)                        //由于減法會(huì)在高位產(chǎn)生0,i的回溯相當(dāng)于去掉無(wú)用的高位0
    {
        i++;
    }
    n=n-i+1;                                          //i回溯后,重新計(jì)算n
    int *temp_sub=result;                              //交換指針,保證結(jié)果實(shí)在*this對(duì)象中
    result=data;
    data=temp_sub;
    delete [] result;
    return *this;
}///:p

cata &cata::operator *(const cata &y)
{
    int len_x=length(),len_y=y.length();
    int len_z=len_x+len_y;
    int *result=new int [len_z];                      //result存放高精度*的結(jié)果
    int *temp=new int [len_z];
    if(NULL==result||NULL==temp)
    {
        cout<<"the error take place in *"<<endl;
        exit(1);
    }
    for(int j=0;j<len_z;j++)
    {
        result[j]=0;
    }    
    int carry,temp1,temp2;                            //carry為進(jìn)位
    for(j=0;j<len_y;j++)                              //模擬手工方法,實(shí)現(xiàn)乘法
    {
        for(int i=0;i<len_z;i++)
        {
            temp[i]=0;
        }
        carry=0;
        for(i=0;i<len_x;i++)
        {
            temp2=temp1=data[i]*y.data[j]+carry;
            carry=temp1/10;
            if(carry)
            {
                temp[i+j]=temp2%10;
            }
            else
            {
                temp[i+j]=temp2;
            }
        }
        if(carry)
        {
            temp[len_x+j]=carry;
        }
        int carry_add=0,temp1_add,temp2_add;          //乘法中的加法
        for(i=0;i<len_z;i++)
        {
            temp2_add=temp1_add=temp[i]+result[i]+carry_add;
            carry_add=temp1_add/10;
            if(carry_add)
            {
                result[i]=temp2_add%10;
            }
            else
            {
                result[i]=temp2_add;
            }
        }
    }
    this->n=len_z;
    int i=1;
    while(result[n-i]==0&&i<n) 
    {
        i++;
    }
    n=n-i+1;
    int *temp_change=result;                          //交換指針
    result=data;