Two Round Dances (Codeforces 1433E)
Tags: Math, combinatorics

One day, $$$n$$$ people ($$$n$$$ is an even number) met on a plaza and made two round dances, each round dance consists of exactly $$$\frac{n}{2}$$$ people. Your task is to find the number of ways $$$n$$$ people can make two round dances if each round dance consists of exactly $$$\frac{n}{2}$$$ people. Each person should belong to exactly one of these two round dances.Round dance is a dance circle consisting of $$$1$$$ or more people. Two round dances are indistinguishable (equal) if one can be transformed to another by choosing the first participant. For example, round dances $$$[1, 3, 4, 2]$$$, $$$[4, 2, 1, 3]$$$ and $$$[2, 1, 3, 4]$$$ are indistinguishable.For example, if $$$n=2$$$ then the number of ways is $$$1$$$: one round dance consists of the first person and the second one of the second person.For example, if $$$n=4$$$ then the number of ways is $$$3$$$. Possible options:  one round dance — $$$[1,2]$$$, another — $$$[3,4]$$$;  one round dance — $$$[2,4]$$$, another — $$$[3,1]$$$;  one round dance — $$$[4,1]$$$, another — $$$[3,2]$$$. Your task is to find the number of ways $$$n$$$ people can make two round dances if each round dance consists of exactly $$$\frac{n}{2}$$$ people.

Input: The input contains one integer $$$n$$$ ($$$2 \le n \le 20$$$), $$$n$$$ is an even number.

Output: Print one integer — the number of ways to make two round dances. It is guaranteed that the answer fits in the $$$64$$$-bit integer data type.


Sample Inputs:
2

4

8

20

Sample Outputs:
1

3

1260

12164510040883200

Solution (Python):
from collections import *
from itertools import *
from bisect import *
from heapq import *
from math import ceil, prod, gcd, factorial
from time import time
mod = 10 ** 9 + 7
d = ((1, 0), (0, 1), (0, -1), (-1, 0))
alpha = 'abcdefghijklmnopqrstuvwxyz'
for _ in range(1):
    n = int(input())
    res = factorial(n // 2 - 1)
    for i in range(n - 1, n // 2, -1):
        res *= i
    print(res)

Solution (Python):
n = int(input())
fac = 1
hfac = 1
for i in range(1, n // 2 + 1):
    hfac = hfac * i
for i in range(1, n + 1):
    fac = fac * i
sel = fac // (hfac * hfac)
print(fac // (hfac * hfac) * (hfac // (n // 2)) ** 2 // 2)

Solution (Python):
from math import factorial
n = int(input())
total_ways = factorial(n) / (factorial(n // 2) * factorial(n // 2)) * factorial(n // 2 - 1) ** 2 / 2
print(int(total_ways))