#P2084. Game of Connections

    ID: 1085 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>高精度组合数学Catalan数列Shanghai 2004 Preliminary

Game of Connections

题目描述:

这是一个古老而简单的游戏。你需要将数字 11, 22, 33, ..., 2n2n - 11, 2n2n 按顺时针顺序依次写在地上,形成一个圆圈。然后,用一些直线段将这些数字两两配对连接起来。每个数字必须恰好与另一个数字配对连接。

并且,不允许任何两条线段相交。

这仍然是一个简单的游戏,不是吗?但是,在你写下这 2n 个数字后,你能告诉我共有多少种不同的方式可以将这些数字配对连接起来吗?生活变得更难了,对吧?

输入:

输入文件的每一行是一个正整数 nn,最后一行是一个数字 1-1(表示输入结束)。 你可以假设 11nn100100

输出:

对于每个 nn,输出一行,表示将 2n2n 个数字配对连接的方式数目。

示例输入:

2
3
-1

示例输出:

2
5

来源:

2004年上海赛区初赛