hdu 1023 Train Problem II 这题运用到大数相乘+大数相除+卡特兰
发布时间：2020-12-14 02:40:17 所属栏目：大数据 来源：网络整理
导读：Train Problem II Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6454????Accepted Submission(s): 3514 Problem Description As we all know the Train Problem I,the boss of the Ignatius
Train Problem IITime Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6454????Accepted Submission(s): 3514
Problem Description
As we all know the Train Problem I,the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order,how many orders that all the trains can get out of the railway.
?
Input
The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.
?
Output
For each test case,you should output how many ways that all the trains can get out of the railway.
?
Sample Input
?
Sample Output
?
卡特兰数：百度百科
代码：
#include <stdio.h>
int cat[110][100] ;
int main()
{
int n ;
cat[0][0] = cat[1][0] = 1 ;
cat[0][1] = cat[1][1] = 1 ;
for(int i = 2 ; i <= 100 ; ++i)
{
for(int j = 1 ; j <= cat[i-1][0] ; ++j)
{
cat[i][j] = cat[i-1][j]*(4*i-2) ;
}
int temp = 0,len = 1;
for(len = 1 ; len <= cat[i-1][0] ; ++len)
{
cat[i][len] += temp ;
temp = cat[i][len]/10 ;
cat[i][len] %= 10 ;
}
while(temp != 0)
{
cat[i][len++] += temp%10 ;
temp /= 10 ;
}
for(int j = len-1,r = 0; j > 0 ; --j)
{
temp = r*10+cat[i][j] ;
r = temp%(i+1) ;
cat[i][j] = temp/(i+1) ;
}
while(cat[i][len] == 0)
{
--len ;
}
cat[i][0] = len ;
}
while(~scanf("%d",&n))
{
for(int i = cat[n][0] ; i > 0 ; --i)
printf("%d",cat[n][i]) ;
puts("") ;
}
return 0 ;
}
与君共勉 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |