这篇博客是从旧博客 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;
}