Разбор

Сначала следует выбрать $n /2$ людей для первого хоровода. Это можно сделать $C_{n}^{n /2}$ способами. Подсчитаем количество способов, которыми можно поставить людей внутри одного хоровода. Зафиксируем того кто будет первым, после чего остальных $n /2 - 1$ людей можно расставить произвольным образом, а именно $(n /2 - 1)!$ способами. Количество способов составить два хоровода равно

C_{n}^{n /2} \cdot (n /2 - 1)! \cdot (n /2 - 1)! / 2

Деление на $2$ необходимо чтобы не различать пары хороводов $(x, y)$ и $(y, x)$ . Например, при $n = 4$ разделения на хороводы $([1, 2], [3, 4])$ и $([3, 4], [1, 2])$ будем считать одинаковыми.

Упростим указанную формулу и получим ответ:

\frac{n !}{( n /2 )! \cdot ( n /2 )!} \cdot (n /2 - 1)! \cdot (n /2 - 1)! / 2 = \frac{1}{2} \cdot \frac{n !}{( n /2 ) \cdot ( n /2 )} = \frac{2 \cdot n !}{n \cdot n} = \frac{2 \cdot ( n - 1 )!}{n}

Пример

Например, при $n = 4$ количество способов равно $3$ :

первый раунд танца — $[1, 2]$ , второй — $[3, 4]$ ;
первый раунд танца — $[2, 4]$ , второй — $[3, 1]$ ;
первый раунд танца — $[4, 1]$ , второй — $[3, 2]$ .

По формуле для $n = 4$ ответ равен

\frac{2 \cdot ( 4 - 1 )!}{4} = \frac{12}{4} = 3

Построим все различимые хороводы для $n = 4$ . На первом месте поставим участника $1$ . На остальных трех местах можно поставить любую перестановку из трех остальных участников.

Вращая по кругу любую из приведенных расстановок, можно получить неразличимые хороводы. Например, неразличимыми будут (рассмотрим циклические сдвиги последней перестановки):

[1, 4, 3, 2], [2, 1, 4, 3], [3, 2, 1, 4], [4, 3, 2, 1]

Имеется $4! = 24$ хороводов из $4$ участников. Однако различимых хороводов для $n = 4$ имеется $3! = 6$ .

Реализация алгоритма

Функция fact вычисляет факториал числа $n$ .

long long fact(int n)
{
  long long res = 1;
  for (int i = 2; i <= n; i++)
    res *= i;
  return res;
}

Основная часть программы. Читаем входное число $n$ .

scanf("%d", &n);

Вычисляем и выводим ответ.

res = 2 * fact(n - 1) / n;
printf("%lld\n", res);

Python реализация

Функция fact вычисляет факториал числа $n$ .

def fact(n):
  res = 1
  for i in range(2, n + 1):
    res *= i
  return res

Основная часть программы. Читаем входное число $n$ .

n = int(input())

Вычисляем и выводим ответ.

res = 2 * fact(n - 1) // n
print(res)