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

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

时间限制: 1 Sec  内存限制: 128 MB
提交: 12  解决: 5
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][44kb]

题目描述

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

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

输入

    一个正整数n

输出

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

样例输入

5

样例输出

5

提示

来源

[提交][状态]