hdoj1023.txt

北京大学 在线acm在线判题系统 一些题目解答

/*
   农夫三拳@seu
   drizzlecrj.gmail.com
   2007-03-02
*/
#include <iostream>
#include <memory>
#include <string>
using namespace std;

typedef int hugeint;

const int Base = 10000;  //应不大于10000,以防乘法时溢出。
const int Capacity = 200;

struct xnum
{
    int Len;
    int Data[Capacity];
    xnum() : Len(0) {}
    xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); }
    xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; }
    xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; }
    int& operator[](int Index) { return Data[Index]; }
    int operator[](int Index) const { return Data[Index]; }
};


int compare(const xnum& A, const xnum& B)
{
    int I;
    if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1;
    for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--);
    if (I < 0) return 0;
    return A[I] > B[I] ? 1 : -1;
}

xnum operator+(const xnum& A, const xnum& B)
{
    xnum R;
    int I;
    int Carry = 0;
    for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++)
    {
        if (I < A.Len) Carry += A[I];
        if (I < B.Len) Carry += B[I];
        R[I] = Carry % Base;
        Carry /= Base;
    }
    R.Len = I;
    return R;
}

xnum operator*(const xnum& A, const int B)
{
    int I;
    if (B == 0) return 0;
    xnum R;
    hugeint Carry = 0;
    for (I = 0; I < A.Len || Carry > 0; I++)
    {
        if (I < A.Len) Carry += hugeint(A[I]) * B;
        R[I] = Carry % Base;
        Carry /= Base;
    }
    R.Len = I;
    return R;
}

xnum operator/(const xnum& A, const int B)
{
    xnum R;
    int I;
    hugeint C = 0;
    for (I = A.Len - 1; I >= 0; I--)
    {
        C = C * Base + A[I];
        R[I] = C / B;
        C %= B;
    }
    R.Len = A.Len;
    while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--;
    return R;
}

ostream& operator<<(ostream& Out, const xnum& V)
{
    int I;
    Out << (V.Len == 0 ? 0 : V[V.Len - 1]);
    for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10;
    return Out;
}

xnum catalan[101];

void Init()
{
	int i, j;
	xnum result;
	for(i = 1; i < 101; ++i)
	{
		result = 1;
		for(j = i + 2; j <= i + i; j++)
			result = result * j;
		for(j = 2; j <= i; j++)
			result = result / j;
		catalan[i] = result;
	}
}

int main()
{
	Init();
    int n;
	while(cin >> n)
	{
		cout << catalan[n] << endl;
	}
    return 0;
}