Problem 26400 --【递推】Ⅳ.Catalan数(例题)

26400: 【递推】Ⅳ.Catalan数(例题)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 12  Solved: 5
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][44kb]

Description

    Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的,它经常出现在组合计数问题中。

    问题的提出:在一个凸n边形中,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同的拆分数目用hn表示,hn即为Catalan数。例如五边形有如下五种拆分方案,故h5=5。求对于一个任意的凸n边形相应的hn

Input

    一个正整数n

Output

    Catalan数(所有数据均在long范围内)。

Sample Input

5

Sample Output

5

HINT

Source

[Submit][Status]