Train?Problem?II

Time?Limit:?2000/1000?MS?(Java/Others)????Memory?Limit:?65536/32768?K?(Java/Others)
Total?Submission(s):?7198????Accepted?Submission(s):?3885

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<math.h>

#include<string.h>

#define?base?10000//四位数字的处理

#define?max?120

using?namespace?std;

int?catalan[max][max];

void?big_mul(int?*a,int?n)

{

????int?temp=0;

????for(int?i=0;i<max;i++)

????{

????????temp+=a[i]*n;

????????a[i]=temp%base;

????????temp/=base;

????}

}

void?big_div(int?*a,int?n)

{

????int?temp=0;

????for(int?i=max-1;i>=0;i--)

????{

????????temp=temp*base+a[i];

????????a[i]=temp/n;

????????temp%=n;

????}

}

void?set()

{

????for(int?i=0;i<max;i++)

????????memset(catalan[i],sizeof(int)*max);

????????catalan[0][0]=1;

????????catalan[1][0]=1;

????????for(int?i=2;i<max;i++)

????????{

????????????memcpy(catalan[i],catalan[i-1],sizeof(int)*max);

????????????big_mul(catalan[i],4*i-2);

????????????big_div(catalan[i],i+1);

?

????????}

?

}

void?output(int?*a,int?n)

{

????int?i=n-1;

????while(a[i]==0)?i--;

????printf("%d",a[i--]);

????while(i>=0)?printf("%04d",a[i--]);

????printf("n");

}

int?main()

{

????set();

????int?t;

????while(~scanf("%d",&t))

????{

????????output(catalan[t],max);

????}

????/*for(int?i=0;i<max;i++)

????????output(catalan[i],max);

????return?0;*/

}

/////////////////////////////下为个人模板0.0

#include<stdio.h>

#include<math.h>

#include<string.h>

#define?base?10000

#define?max?120

using?namespace?std;

int?cat[max][max];

////此处乘除法按照人正常思路去做0.0

void?big_mul(int?*a,int?n)

{

????int?temp=0;//进位系统

????for(int?i=0;i<max;i++)

????{

????????temp+=a[i]*n;

????????a[i]=temp%base;

????????temp/=base;

????}

}

void?big_div(int?*a,int?n)

{

????int?temp=0;

????for(int?i=max-1;i>=0;i--)

????{

????????temp=temp*base+a[i];

????????a[i]=temp/n;

????????temp%=n;

????}

}

void?set()

{

????for(int?i=0;i<max;i++)

?????????memset(cat[i],sizeof(int)*max);//初始化所有数字为零?保证无脑乘除法的过程中没有乱数字的情况.

????cat[0][0]=1;

????cat[1][0]=1;

????for(int?i=2;i<max;i++)

????{

????????memcpy(cat[i],cat[i-1],sizeof(int)*max);//按照字节复制?保证数据值不变.

????????big_mul(cat[i],4*i-2);

????????big_div(cat[i],i+1);

????}

}

void?output(int?*a,int?n)

{

????int?i=n-1;

????while(a[i]==0)i--;

????printf("%d",a[i--]);

????while(i>=0)printf("%04d",&t))

????{

????????output(cat[t],max);

????}

}