Description
The director of a new movie needs to create a scaled set for the movie. In the set there will be
N skyscrapers, with distinct integer heights from 1 to
N meters. The skyline will be determined by the sequence of the heights of the skyscrapers from left to right. It will be a permutation of the integers from 1 to
N.
The director is extremely meticulous, so she wants to avoid a certain sloping pattern. She doesn't want for there to be ANY three buildings in positions
i, j and
k, i < j < k, where the height of building
i is smaller than that of building
j, and building j's height is smaller than building
k's height.
Your task is to tell the director, for a given number of buildings, how many distinct orderings for the skyline avoid the sloping pattern she doesn't like.
Input
There will be several test cases in the input. Each test case will consist of a single line containing a single integer
N (3
N
1,
000), which represents the number of skyscrapers. The heights of the skyscrapers are assumed to be
1, 2, 3,..., N. The input will end with a line with a single
0.
Output
For each test case, output a single integer, representing the number of good skylines - those avoid the sloping pattern that the director dislikes -
modulo 1,000,000. Print each integer on its own line with no spaces. Do not print any blank lines between answers.
catalan数
/*#include<cstdio>
#include<algorithm>
using namespace std;
#define mod 1000000
int main(){
int n,i,j,k,sum,s[1010],f;
//while(scanf("%d",&n))
for(n=3;n<=20;n++){
if(n==0)break;
for(i=1;i<=n;i++)
s[i]=i;
sum=0;
do{
f=1;
for(i=1;i<=n && f;i++)
for(j=i+1;j<=n && f;j++)
for(k=j+1;k<=n && f;k++){
if(s[i]<s[j] && s[j]<s[k]){
f=0;
break;
}
}
if(f)sum++;
}while(next_permutation(s+1,s+n+1));
printf(" %d = %d\n",n,sum);
}
}*/
#include<cstdio>
#define mod 1000000
long long h[1010];
int main(){
int n,i,j;
h[0]=1;h[1]=1;
for(i=2;i<=1000;i++){
for(j=0;j<=i-1;j++)
h[i]=(h[i]+h[j]*h[i-1-j])%mod;
}
while(scanf("%d",&n)){
if(n==0)break;
printf("%lld\n",h[n]);
}
}
分享到:
相关推荐
Catalan数知识介绍~~~~~呵呵~~~~大家顶顶
Total(n)的递归公式如下,这是Catalan数: Total(n) = for i=1 to n-1 sum(Total(i) * Total(n-i)) if n>=2 Total(n)=1 if n=1 考虑到计算Total(n)时,所有小于规模n的Total(n-1),…,Total(1)都可能被计算多次, ...
Catalan数 Catalan numbers 的公式: Cn=C(2n,n)/(n+1);1 Cn+1=C(2n+2,n+1)/(n+2);2 由1和2推出 Cn/C(n+1)=(n+2)/(4n+2); 而且,对于一个具有n个节点的数的形态的数目 也是同样。。 下面来自:...
首先给出了Catalan数的4个经典组合模型:凸多边形的三角剖分问题、简单有序根树的计数问题、路径问题、乘法结合方式问题,给出了Catalan数的4种推导方法:迭代递推方法、生成函数方法、组合求差方法和一一映射方法,并...
第1章 Catalan猜想与竞赛试题 1.1 引言 1.2 与CataIan猜想有关的竞赛题 1.3 利用Cata]an猜想编拟的竞赛训练题 1.4 几个集训队试题 1.5 关于Catalan猜想的一些进展 第2章 Catalan猜想面向中学生的历史简介 2.1 问题的...
catalan number introduction
卡特兰数(英语:Catalan number),又称卡塔兰数、明安图数,是组合数学中一种常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡特兰的名字来命名。1730年左右被蒙古族数学家明安图使用于对三角函数幂...
很著名的一个组合数, 有详细的推导过程
中国数学家明安图在其《割团密率捷法》中最先应用了Catalan数,取得优秀的研究成果.本文简介明安图的计数成就和Catalan数,综述国内外对明安图应用该数的研究.特别地,近两年来英国的Larcombe发表了5篇文章,对明安图...
Catalan应用 输出所有N对合法括号序列 输出所有已知进栈序列的合法出栈序列 http://blog.csdn.net/ssuchange/article/details/17394609
关于Catalan数列的详细介绍,总结的非常到位细致,值得一看,它是组合数学的经典
组合数学- 卡特兰数列(Catalan).rar
组合数学领域 Catalan数的应用研究 吉林大学软件学院 1.卡特兰数简介 卡特兰数(Catalan Number)是组合数学中应用广泛的重要计数函数,以比利时的数学家欧仁·查理·卡塔兰(1814–1894)的名字来命名,其前几项为...
组合计数问题包含组合数、排列数、错排问题、Lucas定理、广义容斥原理、Catalan数等多个方面。 组合数 组合数是指从n个元素中选取m个元素的方法数,记为C(n, m)或Cnm,计算公式为: C(n, m) = n! / (m! * (n-m)!) ...
1.引言Catalan 數 [10] 原始定義為符合遞迴關係式的數列, 可算出其一般式為cn =其前幾項為Catalan數有許多種組合解釋, 其中一種是指利用
特殊的数系列之卡特兰数(Catalan) 1.括号化问题。矩阵链乘: P=A1×A2×A3×……×An,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案? 2.将多边行划分为三角形问题。将一个凸...
物块移动问题更清楚解释,更详细的解释,科学移动。初学者简单易看懂的代码!!!
兔子繁殖问题 昆虫繁殖 Hanoi塔问题 平面分割问题 杨辉三角 Catalan数 实数数列 贮油点 方格取数
6.3 Catalan数 6.4 第二类Stirling 习题六 第七章 Pólya原理 7.1 等价关系、群、置换群 7.2 Burnside引理 7.3 Pólya定理 习题七 第八章 组合设计 8.1 问题的题出 8.2 魔方与魔和 8.3 拉丁方的构造 8.4 构造奇数阶...
(2)斐波那契数列的通项公式为(3)3.2 Catalan数(1)Catalan数满足递推方程(2)前几个Catalan数为1,1,2,5,14,42,132,