2766: 爱情公寓
题目描述
Er-pang住在爱情公寓里。
爱情公寓是一个圆形建筑，2n个房间都分布园的边上。有n对情侣，一个人住一间房，er-pang和骚姐也住在公寓里面。公寓里的每个帅哥每天都会去自己喜欢的MM房间里（不要YY），他们都会走直线。因为他们不愿意在去陪自己女朋友的路上撞见别人，所以要求所有人的路线不能相交。请问公寓里有多少种住下这n对情侣的方法。两间房住一对情侣算一种（举个例子，A，B两间房住1号情侣，男住A女住B和男住B女住A算一种，其实就是问你圆上不想交的连线方案）。
输入
输出
仅一个整数为方案数。
样例输入 复制
3
样例输出 复制
5
提示
样例解释：假设圆上的6个点顺次为1,2,3,4,5,6
方案一，（1,2），（3,4），（5,6）
方案二，（1,2），（3,6），（4,5）
方案三，（1,4），（2,3），（5,6）
方案四，（1,6），（2,3），（4,5）
方案五，（1,6），（2,5），（3,4）
数据范围
30% n<=100
100% n<=20000
为了让题目更简单，告诉你这是卡特兰数……并附上公式：
令h(0)=1,h(1)=1，catalan数满足递推式[1]：
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,...)