首页 > 代码库 > CSU 1320 Scoop water (卡特兰数)
CSU 1320 Scoop water (卡特兰数)
1320: Scoop water
Time Limit: 2 Sec Memory Limit: 128 MBSubmit: 494 Solved: 129
[Submit][Status][Web Board]
Description
zzy今天刚买了两个水瓢A和B，容量都是为1升，童心未泯的他打算用这个水瓢来玩游戏。
首先zzy准备了一个容量可看作无穷大的水缸，刚开始水缸是空的，然后用水瓢A往水缸里加水，用水瓢B把水缸里的水舀出去，当使用 水瓢B把水舀出去时水缸里必须要至少有1升的水。这样子使用N次水瓢A，也使用N次水瓢B，最后水缸会依旧空的。
Input
输入有多个例子，直到文件结束。
每个例子仅含一个数N(0<N<=10000)，表示你必须使用N次A水瓢和N次B水瓢。
Output
对于每个例子，请输出一个数，表示一共有多少种正确的舀水方式使得舀水过程中 使用B水瓢时水缸里总会有足够的水。
（由于数字比较大，输出的答案模1000000007）
Sample Input
12Sample Output
12HINT
CSU_CX
Source
CSU Monthly 2013 Oct.
卡特兰数关于出栈次序的应用
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<stdlib.h> 5 #include<algorithm> 6 using namespace std; 7 const int mod=1000000007; 8 long long f[10005]; 9 int n;10 int main()11 {12 //freopen("in.txt","r",stdin);;13 f[0]=1;14 for(int i=1;i<=10000;i++)15 for(int j=0;j<i;j++)16 f[i]=((f[j]*f[i-1-j])%mod+f[i])%mod;17 18 while(scanf("%d",&n)!=EOF)19 {20 printf("%lld\n",f[n]);21 }22 return 0;23 }
CSU 1320 Scoop water (卡特兰数)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。