Everyone Loves Permutations (Editorial)

Кожну перестановку можна розбити на "цикли".

Позначимо p^k(i) = p[p^{k-1}(i)], і $p^0(i)=i$. Будемо перебирати $k$ за зростанням з $1$. Колись ми зациклимось, тому що прийдемо в якийсь елемент, де вже були.

1. Чому це колись станеться? Якби ми не знайшли такий цикл, то це означало що в нас є нескінченно багато елементів в перестановці.

2. Чому це буде саме цикл? Якби це був не цикл, то для якогось числа $x$ його число входжень у перестановку було більше за $1$.

Ми розбили перестановку на цикли. Тепер треба порахувати суму індексів. Розвернемо цикл в іншу сторону, щоб йти так, як нам сказано в задачі. Тоді, нам залишається тільки зробити префіксні суми на цих циклах і акуратно підрахувати відповідь — порахувати скільки разів цикл повність пройдеться, і скільки ще елементів після повного проходу воно обійде.

Асимптотика — $\mathcal{O}(N)$