HDU1023 Train Problem II【Catalan数】

题目链接：

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

题目大意：

一列N节的火车以严格的顺序到一个站里。问出来的时候有多少种顺序。

解题思路：

典型的求Catalan数的题目，可是结果会非常大，所以须要用大数来解决。

Catalan公式为 h(n) = h(n-1) * (4*n-2) / (n + 1)，h(0) = h(1) = 1。

AC代码：

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

const int MAXN = 100;

const int BASE = 10000;

void Multiply(int A[], int Max, int b)  //大数乘法 A[]*b 10000进制

{

    int Array = 0;

    for(int i = Max - 1; i >= 0; --i)

    {

        Array += b * A[i];

        A[i] = Array % BASE;

        Array /= BASE;

    }

}

void Divide(int A[], int Max, int b)    //大数除法 A[]/b 10000进制

{

    int Div = 0;

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

    {

        Div = Div * BASE + A[i];

        A[i] = Div / b;

        Div %= b;

    }

}

int A[MAXN+10][MAXN+10];

int main()

{

    memset(A,0,sizeof(A));

    A[1][99] = 1;

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

    {

        for(int j = 0; j < 100; ++j)

            A[i][j] = A[i-1][j];

        Multiply(A[i], MAXN, 4*i-2);

        Divide(A[i], MAXN, i+1);

    }

    int N;

    while(~scanf("%d",&N) && N != -1)

    {

        int i;

        for(i = 0; i < MAXN && A[N][i] == 0; ++i);  //去掉数组前导0

        printf("%d",A[N][i++]); //输出第一个非0数

        for(; i < MAXN; ++i)    //输出后边的数，每位保持4位长度

            printf("%04d",A[N][i]);

        printf("\n");

    }

    return 0;

}