一道趣题（catalan数）
Description
The director of a new movie needs to create a scaled set for the movie. In the set there will be
N
1, 000), which represents the number of skyscrapers. The heights of the skyscrapers are assumed to be/*#include<cstdio>#include<algorithm>using namespace std;#define mod 1000000int 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 1000000long 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]); }}
