Blog·Tanky WooABOUTRSS

HDOJ 1023 | HDOJ 1130 | HDOJ 1134 | BUCT OJ 1222 大数的卡特兰数

14 Sep 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

HDOJ 1023 Train Problem II http://acm.hdu.edu.cn/showproblem.php?pid=1023

HDOJ  1130 How Many Trees? http://acm.hdu.edu.cn/showproblem.php?pid=1130

HDOJ 1134  Game of Connections  http://acm.hdu.edu.cn/showproblem.php?pid=1134

BUCT OJ 1222  连线游戏  http://coder.buct.edu.cn/oj/Problem.aspx?pid=1222

这四题都是大数的卡特兰数,并且基本上可以说这四题的代码通用,唯一的区别就已在输入控制时可能不一样。

这里给出代码,注意在输出时要变通下:

#include 
using namespace std;
const int MAX = 105;
int catalan[105][MAX];
int temp[MAX];

int main()
{
    memset(catalan, 0, sizeof(catalan));
    catalan[1][0] = 1;
    int i, j;
    for(i = 2; i <= 100; ++i)
    {
        int mode = 4*i-2;
        for(j=0; j= 10)
            {
                catalan[i][j+1] += catalan[i][j]/10;
                catalan[i][j] %= 10;
            }
        }
        memset(temp, 0, sizeof(temp));
        int res = 0;
        mode = i+1;
        for(j=MAX-1; j>=0; --j)
        {
            temp[j] = (10*res + catalan[i][j])/mode;
            res = (10*res + catalan[i][j])%mode;
        }
        for(j=0; j<MAX; ++j)
            catalan[i][j] = temp[j];

    }
    int N;
    while(scanf("%d", &N;) && N!=-1)
    {
        i = MAX-1;
        while(catalan[N][i] == 0)
        {
            --i;
        }
        printf("%d", catalan[N][i]);
        while(i--)
            printf("%d", catalan[N][i]);
        printf("\n");
    }
    return 0;
}