uva 10303

卡特兰数  但是个高精度 一开始用最普通的递推式 超时了 百度百科了一下 用另类递推式过了 ~~

这个大数类是做数据结构课程设计的时候写的...

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <vector>

#include <sstream>

#include <string>

#include <cstring>

#include <algorithm>

#include <iostream>

#define maxn 1010

#define INF 0x7fffffff

#define inf 10000000

#define MOD 34943

#define ull unsigned long long

#define ll long long

using namespace std;

#define MAXN 9999

#define MAXSIZE 10

#define DLEN 4

class BigNum

{

private:

    int a[500];    //可以控制大数的位数

    int len;       //大数长度

public:

    BigNum()

    {

        len = 1;    //构造函数

        memset(a,0,sizeof(a));

    }

    BigNum(const int);       //将一个int类型的变量转化为大数

    BigNum(const BigNum &);  //拷贝构造函数

    BigNum &operator=(const BigNum &);   //重载赋值运算符，大数之间进行赋值运算

    friend ostream& operator<<(ostream&,  BigNum&);   //重载输出运算符

    BigNum operator/(const int   &) const;

    BigNum operator+(const BigNum &) const;   //重载加法运算符，两个大数之间的相加运算

    BigNum operator*(const BigNum &) const;   //重载乘法运算符，两个大数之间的相乘运算

};

BigNum::BigNum(const int b)     //将一个int类型的变量转化为大数

{

    int c,d = b;

    len = 0;

    memset(a, 0, sizeof(a));

    while(d > MAXN)

    {

        c = d - (d / (MAXN + 1)) * (MAXN + 1);

        d = d / (MAXN + 1);

        a[len++] = c;

    }

    a[len++] = d;

}

BigNum::BigNum(const BigNum & T) : len(T.len)  //拷贝构造函数

{

    memset(a, 0, sizeof(a));

    for(int i = 0 ; i < len ; i++)

        a[i] = T.a[i];

}

BigNum & BigNum::operator=(const BigNum & n)   //重载赋值运算符，大数之间进行赋值运算

{

    len = n.len;

    memset(a,0,sizeof(a));

    for(int i = 0 ; i < len ; i++)

        a[i] = n.a[i];

    return *this;

}

ostream& operator<<(ostream& out,  BigNum& b)   //重载输出运算符

{

    int i;

    cout << b.a[b.len - 1];

    for(i = b.len - 2 ; i >= 0 ; i--)

    {

        cout.width(DLEN);

        cout.fill('0');

        cout << b.a[i];

    }

    return out;

}

BigNum BigNum::operator+(const BigNum & T) const   //两个大数之间的相加运算

{

    BigNum t(*this);

    int i,big;      //位数

    big = T.len > len ? T.len : len;

    for(i = 0 ; i < big ; i++)

    {

        t.a[i] +=T.a[i];

        if(t.a[i] > MAXN)

        {

            t.a[i + 1]++;

            t.a[i] -=MAXN+1;

        }

    }

    if(t.a[big] != 0)

        t.len = big + 1;

    else

        t.len = big;

    return t;

}

BigNum BigNum::operator*(const BigNum & T) const   //两个大数之间的相乘运算

{

    BigNum ret;

    int i,j,up;

    int temp,temp1;

    for(i = 0 ; i < len ; i++)

    {

        up = 0;

        for(j = 0 ; j < T.len ; j++)

        {

            temp = a[i] * T.a[j] + ret.a[i + j] + up;

            if(temp > MAXN)

            {

                temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);

                up = temp / (MAXN + 1);

                ret.a[i + j] = temp1;

            }

            else

            {

                up = 0;

                ret.a[i + j] = temp;

            }

        }

        if(up != 0)

            ret.a[i + j] = up;

    }

    ret.len = i + j;

    while(ret.a[ret.len - 1] == 0 && ret.len > 1)

        ret.len--;

    return ret;

}

BigNum BigNum::operator/(const int & b) const   //大数对一个整数进行相除运算

{

    BigNum ret;

    int i,down = 0;

    for(i = len - 1 ; i >= 0 ; i--)

    {

        ret.a[i] = (a[i] + down * (MAXN + 1)) / b;

        down = a[i] + down * (MAXN + 1) - ret.a[i] * b;

    }

    ret.len = len;

    while(ret.a[ret.len - 1] == 0 && ret.len > 1)

        ret.len--;

    return ret;

}

BigNum f[maxn];

void init()

{

    f[0] = f[1] = 1;

    for(int i = 2; i <= 1000; ++ i)

        f[i] = f[i-1] * (4*i-2) / (i+1);

}

int main()

{

    init();

    int n;

    while(scanf("%d", &n) == 1)

        cout << f[n] << endl;

    return 0;

}