Круглий стіл#11679

Круглий стіл (Розбір)

На відміну від розташування в ряд, у круглого столу немає фіксованого початку. Тому всі розстановки, які відрізняються тільки циклічним зсувом, вважаються однаковими.

Якби люди розташовувались у ряд, то кількість способів була б рівна $n!$ , так як можна довільно переставляти $n$ різних людей.

Для круглого столу кожне конкретне розміщення можна повернути $n$ способами, отримавши $n$ еквівалентних лінійних перестановок.

Наприклад, для розміщення $(1, 2, 3, 4)$ (1, 2, 3, 4) повороти дають:

(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)

(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)

Усі ці розміщення вважаються однаковими.

Отже, кожне унікальне кругове розміщення відповідає рівно $n$ лінійним перестановкам.

Щоб отримати число різних розсадок навколо круглого столу, потрібно загальну кількість перестановок розділити на кількість еквівалентних поворотів:

\frac{n !}{n} = (n - 1)!

\frac{n!}{n} = (n - 1)!

Приклад

Для $4$ людей існує $6$ різних розташувань:

$(1, 2, 3, 4)$ (1, 2, 3, 4)
$(1, 2, 4, 3)$ (1, 2, 4, 3)
$(1, 3, 2, 4)$ (1, 3, 2, 4)
$(1, 3, 4, 2)$ (1, 3, 4, 2)
$(1, 4, 2, 3)$ (1, 4, 2, 3)
$(1, 4, 3, 2)$ (1, 4, 3, 2)

Усі решта розташувань за допомогою повороту можна звести до одного із перелічених. Наприклад, розташування $(4, 2, 1, 3)$ (4, 2, 1, 3) еквівалентне розташуванню $(1, 3, 4, 2)$ (1, 3, 4, 2).

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

Читаємо вхідне значення $n$ .

scanf("%lld", &n);

У змінній $r es$ обчислюємо відповідь.

res = 1;
for (i = 1; i < n; i++)
  res = res * i;

Виводимо відповідь.

printf("%lld\n", res);