Порядок перестановки#1789

Порядок перестановки (Розбір)

Нехай $p$ — задана перестановка, а $p [i]$ — елемент перестановки, який знаходиться на позиції $i$ . Розглянемо послідовність елементів: $i, p [i], p [p [i]]$ i, p[i], p[p[i]], .... Оскільки кількість елементів у перестановці кінцева, існує таке мінімальне $k$ , що $p [i]^{k} = i$ p[i]^k = i. Послідовність елементів $i, p [i], p [p [i]], ..., p [i]^{k - 1}$ i, p[i], p[p[i]], ..., p[i]^{k-1}, для якої $p [i]^{k} = i$ p[i]^k = i, будемо називати циклом. Довжина циклу дорівнює $k$ .

Будь-яку перестановку можна подати у вигляді списку циклів. Наприклад, перестановка $[4, 3, 2, 5, 1, 6]$ [4, 3, 2, 5, 1, 6] представляється як $(1, 4, 5) (2, 3) (6)$ (1, 4, 5)(2, 3)(6).

Наприклад, послідовність $(1, p [1], p [p [1]]) = (1, 4, 5)$ (1, p[1], p[p[1]]) = (1, 4, 5) утворює цикл, оскільки $p [p [p [1]]] = p [1]^{3} = 1$ p[p[p[1]]] = p[1]^3 = 1. Довжина цього циклу дорівнює $3$ .

Ступінь перестановки дорівнює НСК довжин її циклів.

Приклад

У першому прикладі перестановка $[4, 3, 2, 5, 1, 6]$ [4, 3, 2, 5, 1, 6] представляється у вигляді $(1, 4, 5) (2, 3) (6)$ (1, 4, 5)(2, 3)(6). Довжини циклів дорівнюють $3, 2$ і $1$ . Ступінь перестановки дорівнює $НСК (3, 2, 1) = 6$ НСК(3, 2, 1) = 6.

У другому прикладі перестановка $[4, 3, 6, 8, 9, 7, 2, 1, 5]$ [4, 3, 6, 8, 9, 7, 2, 1, 5] представляється у вигляді $(1, 4, 8) (2, 3, 6, 7) (5, 9)$ (1, 4, 8)(2, 3, 6, 7)(5, 9). Довжини циклів дорівнюють $3, 4$ і $2$ . Ступінь перестановки дорівнює $НСК (3, 4, 2) = 12$ НСК(3, 4, 2) = 12.

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

Масив $p$ зберігає вхідну перестановку. Масив $u se d$ використовується для позначення оброблених елементів.

#define MAX 101
int p[MAX], used[MAX];

Читаємо вхідну перестановку.

scanf("%d",&n);
for(i = 1; i <= n; i++)
  scanf("%d",&p[i]);

У змінній $r es$ підраховуємо ступінь перестановки $p$ .

res = 1;
memset(used, 0, sizeof(used));

Перебираємо індекси перестановки. Для кожного обробленого індексу $i$ встановлюємо $u se d [i] = 1$ used[i] = 1.

for (i = 1; i <= n; i++)
  if (!used[i])
  {

Цикл з елементом $p [i]$ ще не знайдено. Шукаємо довжину циклу $l e n$ у перестановці, починаючи з індексу $j = i$ j = i. Для цього послідовно переходимо по індексах $j, p [j], p [p [j]]$ j, p[j], p[p[j]], ..., доки не зустрінеться вже пройдений елемент. Усі пройдені індекси $j$ позначаємо як відвідані, встановлюючи $u se d [j] = 1$ used[j] = 1.

    len = 0;
    j = i;
    while (!used[j])
    {
      used[j] = 1;
      j = p[j];
      len++;
    }

C++

Змінна $l e n$ містить довжину поточного знайденого циклу. Обчислюємо НСК довжин всіх циклів.

    res = lcm(res, len);
  }

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

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