Сакурако та дивна перестановка#409

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

Автор:

Богдан Фейса

Підготовка завдання:

Богдан Фейса

Розбір:

Богдан Фейса

Блок : n\le 8:

У цьому рішенні блоку ми спробуємо згенерувати всі можливі списки перестановок і перевірити, чи підходять вони для нашої перестановки . Часова складність O(\binom{\frac{n\cdot(n-1)}{2}}{8}\cdot n). Що менше ніж 2.5\cdot 10^8.

Блок : n\le 100:

Для нашої перестановки ми створимо її циклічну декомпозицію наступним чином:

  1. створити її графічне представлення

  2. обчислити для кожної вершини множину тих, що доступні з неї за O(n^2).

  3. знайти порядок тих чисел у циклі.

Тепер, коли ми маємо циклічну декомпозицію нашої перестановки, ми беремо її транспозиції, і це наша відповідь. Часова складність O(n^2).

Блок : n\le 10^5:

У цьому рішенні блоку ми можемо використовувати O(n\log{n}) час для циклічної декомпозиції перестановки. Коли ми маємо всі цикли, ми записуємо ребра циклів, і це наша відповідь. Тому що, використовуючи ці перестановки, ми створюємо обернену до . І t[t^{-1}[i]]=i, і це те, що нам потрібно знайти.

Блок : повне рішення:

Ми змінюємо наш код, щоб розбити перестановку на цикли за лінійний час. Потім ми записуємо ребра циклу, і це наша відповідь. Часова складність .