HDU Train Problem II

简介:

Train Problem II

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 138 Accepted Submission(s): 80
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
1
2
3
10
 
Sample Output
1
2
5
16796
Hint
The result will be very large, so you may not process it by 32-bit integers.

#include"stdio.h"
#include"string.h"
int ch[101][200]={0};

int temp[200]={0};

int add(int* x,int* y)
{
    int i;
    for(i=0;x[i]!=0&&y[i]!=0;i++)
    {
        x[i]+=y[i]-'0';
    }
    for(i;y[i]!=0;i++)
        x[i]+=y[i];
    int t;
    for(t=0;x[t]!=0;t++)
    {
        if(x[t+1]!=0)
            x[t+1]+=(x[t]-'0')/10;
        else
        {
            if((x[t]-'0')/10!=0)
                x[t+1]+=(x[t]-'0')/10+'0';
            else
                x[t+1]=0;
        }
        x[t]=(x[t]-'0')%10+'0';   
    }
    return t;
}
int* mul(int* x,int* y)
{
    for(int i=0;i<200;i++)
        temp[i]=0;
   
    for(int i=0;x[i]!=0;i++)
        for(int j=0;y[j]!=0;j++)
        {
            if(temp[i+j]!=0)
                temp[i+j]+=(x[i]-'0')*(y[j]-'0');
            else
                temp[i+j]+=(x[i]-'0')*(y[j]-'0')+'0';
           
        }
    int length=0;
    while(temp[length]!=0)
        length++;
    for(int t=0;t<length;t++)
    {
        temp[t+1]+=(temp[t]-'0')/10;
        temp[t]=(temp[t]-'0')%10+'0';
    }
    if(temp[length]!=0)
        temp[length]+='0';
    while(temp[length]!=0)
    {
        if((temp[length]-'0')/10!=0)
            temp[length+1]+=temp[length]/10+'0';
        temp[length]=(temp[length]-'0')%10+'0';
        length++;
    }

    return temp;
}

int main()
{
    ch[0][0]='1';
    ch[1][0]='1';

    for(int i=2;i<=100;i++)
    {
        for(int j=0;j<i;j++)
        {
            add(ch[i],mul(ch[j],ch[i-j-1]));
        }
    }
   
    int n,t=199;
    while(scanf("%d",&n)>0)
    {
        t=199;
        while(t>=0)
        {
            if(ch[n][t]!=0)
                printf("%c",ch[n][t]);
            t--;
        }

        printf("\n");
    }
    return 0;
}








本文转自NewPanderKing51CTO博客,原文链接:http://www.cnblogs.com/newpanderking/archive/2011/07/29/2121146.html ,如需转载请自行联系原作者






相关文章
|
12月前
|
Java
hdu 1022 Train Problem I【模拟出入栈】
hdu 1022 Train Problem I【模拟出入栈】
43 0
hdu 1022 Train Problem I【模拟出入栈】
|
12月前
|
图形学
hdu1086 You can Solve a Geometry Problem too(判断线段相交)
hdu1086 You can Solve a Geometry Problem too(判断线段相交)
69 0
UVa11565 - Simple Equations
UVa11565 - Simple Equations
50 0
HDOJ/HDU 1022 Train Problem I(模拟栈)
HDOJ/HDU 1022 Train Problem I(模拟栈)
117 0
HDOJ/HDU 1022 Train Problem I(模拟栈)
|
Java
HDU - 2018 Multi-University Training Contest 2 - 1010: Swaps and Inversions
HDU - 2018 Multi-University Training Contest 2 - 1010: Swaps and Inversions
107 0
|
机器学习/深度学习 自然语言处理