杭电OJ 1023

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1023

开始时看不明白题意，后来才知道要参照1022。其实就是求进出栈的先后次序的排列组合，是一个典型的卡特兰数列。涉及到大数运算，为了避免大数的除法，就不用卡特兰数的通项公式解了，直接用递归式解，这样只要写大数的加法和乘法，以下为AC代码。

#include <cstdio>
#include <cstring>

typedef struct {
    int num_[1000];
    int length_;
} BigNum;

void InitBigNum(BigNum *p_bn, int value)
{
    p_bn->num_[0] = value;
    p_bn->length_ = 1;
}

void CopyBigNum(const BigNum &src, BigNum *p_dest)
{
    p_dest->length_ = src.length_;
    for (int i=0; i<p_dest->length_; ++i) {
	p_dest->num_[i] = src.num_[i];
    }
}

void PrintBigNum(const BigNum &bn)
{
    printf("%d", bn.num_[bn.length_-1]);
    
    int table[4];
    int temp = 1000;
    for (int i=0; i<4; i++) {
	table[i] = temp;
	temp /= 10;
    }

    for (int i=bn.length_-2; i>-1; --i) {
	for (int j=0; j<4; ++j) {
	    printf("%d", bn.num_[i] / table[j] % 10);
	}
    }
    printf("\n");
}

void Add(const BigNum &bn_a, const BigNum &bn_b, BigNum *p_sum)
{
    const BigNum *p_long, *p_short;
    if (bn_a.length_ >= bn_b.length_) {
	p_long = &bn_a;
	p_short = &bn_b;
    } else {
	p_long = &bn_b;
	p_short = &bn_a;
    }

    int co = 0;
    for (int i=0; i<p_short->length_; ++i) {
	int temp = p_long->num_[i] + p_short->num_[i] + co;
	p_sum->num_[i] = temp % 10000;
	co = temp / 10000;
    }

    for (int i=p_short->length_; i<p_long->length_; ++i) {
	int temp = p_long->num_[i] + co;
	p_sum->num_[i] = temp % 10000;
	co = temp / 10000;
    }

    p_sum->length_ = p_long->length_;

    for (int i=p_long->length_; ; ++i) {
	if (co == 0) break;

	p_sum->num_[i] = co % 10000;
	co /= 10000;
	++p_sum->length_;
    }
}

void Mul(const BigNum &bn_a, const BigNum &bn_b, BigNum *p_mul)
{
    const BigNum *p_long, *p_short;

    if (bn_a.length_ >= bn_b.length_) {
	p_long = &bn_a;
	p_short = &bn_b;
    } else {
	p_long = &bn_b;
	p_short = &bn_a;
    }

    p_mul->length_ = p_long->length_ + p_short->length_;
    memset(p_mul->num_, 0, p_mul->length_ * sizeof(int));

    for (int short_index=0; short_index<p_short->length_; ++short_index) {
	int co = 0;
	for (int long_index=0; long_index<p_long->length_; ++long_index) {
	    int temp = p_short->num_[short_index] * p_long->num_[long_index] + co;
	    p_mul->num_[short_index+long_index] += temp % 10000;
	    co = temp / 10000;
	}
	
	for (int i=short_index+p_long->length_; ; ++i) {
	    if (co == 0) break;

	    p_mul->num_[i] += co % 10000;
	    co /= 10000;
	}
    }

    if (p_mul->num_[p_mul->length_-1] == 0) --p_mul->length_;
}

BigNum catalan_array[101];

void InitCatalan()
{
    InitBigNum(&catalan_array[0], 1);
    InitBigNum(&catalan_array[1], 1);

    for (int i=2; i<101; ++i) {
	BigNum sum;
	InitBigNum(&sum, 0);
	for (int j=0; j<i; ++j) {
	    BigNum mul;
	    Mul(catalan_array[j], catalan_array[i-1-j], &mul);
	    BigNum temp;
	    Add(sum, mul, &temp);
	    CopyBigNum(temp, &sum);
	}

	CopyBigNum(sum, &catalan_array[i]);
    }
}

int main()
{
    InitCatalan();
    
    int a;
    while (scanf("%d", &a) != EOF) {
	PrintBigNum(catalan_array[a]);
    }
    
    return 0;
}