区域赛系列一多边形划分(卡特兰数)

区域赛系列一多边形划分

时间限制：1000 ms | 内存限制：65535 KB

难度：2

描述

Give you a convex（凸边形）, diagonal n-3 disjoint divided into n-2 triangles(直线), for different number of methods, such as n=5, there are 5 kinds of partition method, as shown in Figure

输入

The first line of the input is a n (1<=n<=1000), expressed n data set. The next n lines each behavior an integer m (3<=m<=18), namely the convex edges.

输出

For each give m,, output how many classification methods. example output: Case #a : b

样例输入

样例输出

Case #1 : 1
Case #2 : 2
Case #3 : 5

卡特兰数：

卡塔兰数是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。

卡塔兰数的一般项公式为 $C_n = frac{1}{n+1}{2n choose n} = frac{(2n)!}{(n+1)!n!}$ 另类递归式： h(n)=((4*n-2)/(n+1))*h(n-1);

前几项为（OEIS中的数列A000108）: 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(n)=((4*n-2)/(n+1))*h(n-1);

最典型的四类应用：（实质上却都一样，无非是递归等式的应用，就看你能不能分解问题写出递归式了）
1.括号化问题。

　　矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)
2.出栈次序问题。

　　一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
　　类似：
　　(1)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
　　(2)在圆上选择2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数。
3.将多边行划分为三角形问题。

　　将一个凸多边形区域分成三角形区域的方法数?
　　类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她
　　从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
　　类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
4.给顶节点组成二叉树的问题。

　　给定N个节点，能构成多少种形状不同的二叉树？
　　(一定是二叉树!
　　先去一个点作为顶点,然后左边依次可以取0至N-1个相对应的,右边是N-1到0个,两两配对相乘,就是h(0)*h(n-1) + h(2)*h(n-2) + + h(n-1)h(0)=h(n))
　　（能构成h（N）个）

5，问题描述:
12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？

我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排.
用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案.
比如000000111111就对应着
第一排：0 1 2 3 4 5
第二排：6 7 8 9 10 11
010101010101就对应着
第一排：0 2 4 6 8 10
第二排：1 3 5 7 9 11
问题转换为，这样的满足条件的01序列有多少个。
观察1的出现，我们考虑这一个出现能不能放在第二排，显然，在这个1之前出现的那些0,1对应的人
要么是在这个1左边，要么是在这个1前面。而肯定要有一个0的，在这个1前面，统计在这个1之前的0和1的个数。
也就是要求，0的个数大于1的个数。
OK，问题已经解决。
如果把0看成入栈操作，1看成出栈操作，就是说给定6个元素，合法的入栈出栈序列有多少个。
这就是catalan数,这里只是用于栈，等价地描述还有，二叉树的枚举、多边形分成三角形的个数、圆括弧插入公式中的方法数，其通项是c(2n, n)/(n+1)。

代码：

 1 /****c(n,2n)/(n+1)****/
 2 /*#include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 typedef long long LL;
 9 LL fac(int x){
10     LL area=1;
11     for(int i=1;i<=x;i++)area*=i;
12     return area;
13 }
14 int main(){
15     int T,flot=0;
16     LL n;
17     scanf("%d",&T);
18     while(T--){
19         scanf("%lld",&n);
20         n-=2;
21         printf("Case #%d : %lld
",++flot,fac(2*n)/fac(n)/fac(n+1));
22     }
23     return 0;
24 }*/
25 #include<iostream>
26 #include<cstdio>
27 #include<cstring>
28 #include<cmath>
29 #include<algorithm>
30 using namespace std;
31 typedef long long LL;
32 LL m[20];
33 int main(){
34     int T,flot=0;
35     LL n;
36     scanf("%d",&T);
37     m[1]=1;m[2]=2;
38     m[0]=1;
39     int t;
40     for(int i=3;i<=18;i++){
41         m[i]=0;
42         t=i-1;
43         for(int j=0;j<i;j++){
44             m[i]+=m[j]*m[t--];
45         }
46     }
47     while(T--){
48         scanf("%lld",&n);n-=2;
49         printf("Case #%d : %lld
",++flot,m[n]);
50     }
51     return 0;
52 }