Автор: | Богдан Фейса |
Підготовка завдання: | Богдан Фейса |
Розбір: | Богдан Фейса |
Блок : n\le 8:
У цьому рішенні блоку ми спробуємо згенерувати всі можливі списки перестановок і перевірити, чи підходять вони для нашої перестановки . Часова складність O(\binom{\frac{n\cdot(n-1)}{2}}{8}\cdot n). Що менше ніж 2.5\cdot 10^8.
Блок : n\le 100:
Для нашої перестановки ми створимо її циклічну декомпозицію наступним чином:
створити її графічне представлення
обчислити для кожної вершини множину тих, що доступні з неї за O(n^2).
знайти порядок тих чисел у циклі.
Тепер, коли ми маємо циклічну декомпозицію нашої перестановки, ми беремо її транспозиції, і це наша відповідь. Часова складність O(n^2).
Блок : n\le 10^5:
У цьому рішенні блоку ми можемо використовувати O(n\log{n}) час для циклічної декомпозиції перестановки. Коли ми маємо всі цикли, ми записуємо ребра циклів, і це наша відповідь. Тому що, використовуючи ці перестановки, ми створюємо обернену до . І t[t^{-1}[i]]=i, і це те, що нам потрібно знайти.
Блок : повне рішення:
Ми змінюємо наш код, щоб розбити перестановку на цикли за лінійний час. Потім ми записуємо ребра циклу, і це наша відповідь. Часова складність .