Два хороводи#11602

Два хороводи (Розбір)

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

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

C^{n/2}_n \cdot (n / 2 - 1)! \cdot (n / 2 - 1)!~/~2

Ділення на $2$ необхідне, щоб не розрізняти пари кіл $(x, y)$ та $(y, x)$ . Наприклад, для $n = 4$ n = 4, розбиття на кола $([1, 2], [3, 4])$ ([1, 2], [3, 4]) та $([3, 4], [1, 2])$ ([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}

\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$ n = 4 кількість способів дорівнює $3$ :

Одне коло — $[1, 2]$ , інше — $[3, 4]$ ;
Одне коло — $[2, 4]$ , інше — $[3, 1]$ ;
Одне коло — $[4, 1]$ , інше — $[3, 2]$ .

Згідно з формулою для $n = 4$ n = 4, відповідь

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

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

Давайте складемо всі розрізняльні кола для $n = 4$ n = 4. Розмістимо учасника $1$ на першу позицію. На трьох решту позицій можна розмістити будь-яку перестановку трьох інших учасників.

Обертаючи будь-яке з цих розташувань у колі, ми можемо отримати нерозрізняльні кола. Наприклад, такі розташування є нерозрізняльними (розгляньте циклічні зсуви останньої перестановки):

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

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

Є $4! = 24$ 4! = 24 кола з $4$ учасниками. Однак кількість розрізняльних кіл для $n = 4$ n = 4 є $3! = 6$ 3! = 6.

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

Функція fact обчислює факторіал числа $n$ .

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

C++

Основна частина програми. Зчитайте вхідне значення $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)