← 返回题目列表

Codeforces · 1433/E

E. 两轮圆舞

中文机器翻译题面 查看原题

有一天,$$$n$$$人($$$n$$$为偶数)在广场上相遇,跳了两场圆舞,每场圆舞恰好由$$$\frac{n}{2}$$$人组成。你的任务是找出 $$$n$$$ 人跳两段圆舞的方法数,如果每个圆舞正好由 $$$\frac{n}{2}$$$ 人组成。每个人都应该属于这两种圆舞中的一种。

圆舞是由$$$1$$$或更多人组成的舞蹈圈。如果可以通过选择第一个参与者将一个圆舞转变为另一个圆舞,则两个圆舞是无法区分的(相等)。例如,圆舞 $$$[1, 3, 4, 2]$$$、$$$[4, 2, 1, 3]$$$ 和 $$$[2, 1, 3, 4]$$$ 是无法区分的。

例如,如果$$$n=2$$$,则方式数为$$$1$$$:一轮圆舞由第一人组成,第二人为第二人。

例如,如果$$$n=4$$$,则路数为$$$3$$$。可能的选项:

- 一轮舞蹈 — $$$[1,2]$$$,另一场 — $$$[3,4]$$$;
- 一轮舞蹈 — $$$[2,4]$$$,另一场 — $$$[3,1]$$$;
- 一轮舞蹈 — $$$[4,1]$$$,另一场 — $$$[3,2]$$$。

如果每个圆舞恰好由 $$$\frac{n}{2}$$$ 人组成,那么您的任务是找出 $$$n$$$ 人可以跳两段圆舞的方式数量。

输入

输入包含一个整数$$$n$$$ ($$$2 \le n \le 20$$$),$$$n$$$ 为偶数。

输出

打印一个整数——跳两圈圆舞的方式数。保证答案符合 $$$64$$$ 位整数数据类型。

示例

输入 #1

2

输出 #1

1

输入 #2

4

输出 #2

3

输入 #3

8

输出 #3

1260

输入#4

20

输出#4

12164510040883200