Problem25861--爱情公寓

25861: 爱情公寓

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

Er-pang住在爱情公寓里。

爱情公寓是一个圆形建筑,2n个房间都分布园的边上。有n对情侣,一个人住一间房,er-pang和骚姐也住在公寓里面。公寓里的每个帅哥每天都会去自己喜欢的MM房间里(不要YY),他们都会走直线。因为他们不愿意在去陪自己女朋友的路上撞见别人,所以要求所有人的路线不能相交。请问公寓里有多少种住下这n对情侣的方法。两间房住一对情侣算一种(举个例子,AB两间房住1号情侣,男住A女住B和男住B女住A算一种,其实就是问你圆上不想交的连线方案)。

Input

仅一个整数n表示情侣对数。

Output

仅一个整数为方案数。

Sample Input Copy

3

Sample Output Copy

5

HINT

样例解释:假设圆上的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)=1catalan数满足递推式[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

另类递推式[2]

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,...)

Source/Category