Перестановкой называют массив \(a\) длиной \(n\), в котором встречаются все элементы от \(1\) до \(n\).
Например, \(\{1,3,5,4,2\}\) является перестановкой, а \(\{4,1\}\) - нет.
Перестановки используются во многих задачах, в большом количестве задач массивы можно свести к перестановкам, поэтому полезно рассмотреть задачи связанные с ними
Пусть имеется перестановка \(p\) длины \(n\). Мы можем производить следующую операцию: выбрать два соседних элемента и поменять их местами. За какое минимальное количество операций можно отсортировать перестановку?
Оказывается, что минимальное количество операций равно количеству инверсий в перестановке.
Инверсия - это пара чисел \( (i, j) \), \(1 \le i < j \le n \), где \( a_i > a_j \). В отсортированной по возрастанию перестановке число инверсий равно нулю, тогда как в перестановке, отсортированной по убыванию оно равно \(n*(n-1)/2\).
Теперь покажем, что ответ действительно равен количеству инверсий. Возьмём два индекса - \((i, j) \). Если \(a_i < a_j \), нам не нужно менять их положение относительно друг друга, т.к. они уже отсортированы. В противном случае необходимо поменять их местами. Давайте докажем, что если есть хотя бы одна инверсия в перестановке, то найдутся два соседних элемента \(a_i\) и \(a_{i+1}\), чтобы \(a_i > a_{i+1} \). Допустим обратное. Тогда \(a_1 < a_2 < a_3 ... < a_n \). Значит перестановка отсортирована и инверсий нет - пришли к противоречию.
Соберём все факты:
Таким образом, количество операций будет равно количеству инверсий.
Количество инверсий можно посчитать с помощью pbds_tree, дерева отрезков или дерева Фенвика, а также с помощью сортировки слиянием.
Давайте рассмотрим ориентированный граф, образованный перестановкой \(p\). Он состоит из \(n\) вершин и \(n\) ребер, \(i\)-е ребро образуется парой \( (i,p_i) \).
Граф будет состоять из множества простых циклов.
К любому массиву \(a\) можно применить перестановку, тогда \( a'_{p_i} := a_i\). Даная операция ассоциативна, а также обратима (для каждой перестановки существует обратная).
Применение перестановки самой к себе называется возведением перестановки в степень. Соотвественно, можно для нахождения \(k\)-й степени перестановки использовать бинарные (двоичные) подъемы. Асимптотика - \(O(n * \log{k})\)
Теперь рассмотрим граф перестановки. Применение перестановки - сдвиг элементов по циклам в графе. Значит возведению в \(k\)-ю степень равносильны сдвиги по циклу \(j\) ровно на \(k % sz_j \), где \(sz_j\) - размер \(j\)-го цикла. То есть можно находить и за \(O(n)\).
Из-за графа очевидно, что длина периода перестановки (через сколько операций перестановка вернется в исходное положение) - \( НОК(sz_1,sz_2...) \).
Допустим мы хотим проверить: может ли перестановка \(p\) в какой-то степени достичь перестановки \(a\). Во-первых, выпишем все циклы и проверим что в обоих перестановках одинаковые циклы (выпишем циклы в порядке обхода dfs и проверим что два массива являются циклическими сдвигами друг друга).
Теперь по каждому циклу узнаем, насколько должна сдвинуться перестановка.
$$ x_1 \equiv k \pmod{sz_1} $$ $$...$$ $$x_m \equiv k \pmod{sz_m}$$
Где \(k\) - необходимая нам степень. Данная система отсылает нас к Китайской Теореме об Остатках, решение которой и необходимо для окончательного решения задачи.