注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[hdu]1023 Train Problem II  

2012-08-15 10:32:57|  分类: HDU |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一题很经典的利用卡特兰数做的题目。先来简单介绍一下什么是卡特兰数( catalan数 )。
卡特兰数前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

令h(0)=1,h(1)=1,catalan数满足递推式
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)
  例如:h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2
  h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5
另类递推式
h(n)=h(n-1)*(4*n-2)/(n+1);
递推关系的解为:
h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
递推关系的另类解为:
h(n)=c(2n,n)-c(2n,n+1)(n=1,2,3,...)

还想详细了解的可以去百科看看~ http://baike.baidu.com/view/2499752.htm 

题目放出:
还要注意这题的N范围是0~100,是一题大数问题。
所以卡兰特数+大数模板。

Train Problem II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3435    Accepted Submission(s): 1884


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
10
 

Sample Output
16796
Hint
The result will be very large, so you may not process it by 32-bit integers.
 

Author
Ignatius.L



#include<iostream>
#include<cmath>
using namespace std;

int main()
{
int n,m,s;
int i,j,k;
int N[101][101],len[101];
N[1][1] = 1;
N[2][1] = 2;
len[1] = len[2] = 1;
for(i = 3;i <= 100;i ++)
{
for(j = 0;j <= len[i - 1];j ++) //乘法
N[i][j] = N[i - 1][j] *(4 * i - 2);
m = 0;
for(j = 1;j <= len[i - 1];j ++)//乘法处理
{
int a = N[i][j] + m;
N[i][j] = a % 10;
m = a / 10;
}
while(m)
{
N[i][j] = m % 10;
m /= 10;
j ++;
}
s = 0;m = 0;
for(k = j - 1;k >= 1;k --)//除法
{
s=(N[i][k] + m * 10) % (i + 1);
N[i][k] = (N[i][k] + m*10) / (i + 1);
m = s;
}
k = j - 1;
while(N[i][k] == 0)//计算长度
{
k--;
}
len[i] = k;

}

while(cin>>n)
{
for(i = len[n];i >= 1;i--)
cout<<N[n][i];
cout<<endl;
}
}

/*
N(1<=N<=100)
h(n)=h(n-1)*(4*n-2)/(n+1);
Sample Input
1
2
3
10


Sample Output
1
2
5
16796*/




  评论这张
 
阅读(154)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018