O permutacji cyklicznej - algorytm, matematyka, kombinacje, permutacja

Studiowałem matematykę i wpadłem na ten problem. Istnieją dwie permutacje A i B oraz liczba całkowita M. Mówimy A prawie równe B, jeśli możemy wykonać od A do B, wykonując następujące operacje.
-1 Wybierz segment długości M permutacji A.
-2 Wykonaj przesunięcie cykliczne na nim w prawo (więc, jeśli podsegment jest „1 2 3 4 5” (m = 5), to po tej operacji będzie to „5 1 2 3 4”.

Pytanie: Czy A jest prawie równe B?

Myślę, że to typowe, ale nie mogłem znaleźć odpowiedzi. Jak to rozwiązać? (Nie brutalna siła!)

liczba elementów w permutacji <= 10 ^ 5

przykład

„1 2 3”
B „2 3 1”
m = 2
odpowiedz TAK
wyjaśnij „1 2 3” -> „2 1 3” -> „2 3 1”

Odpowiedzi:

1 dla odpowiedzi № 1

Oto dowód mojego przypuszczenia n być długością permutacji i m długość okien, które możemy obracać, gdzie 1 ≤ m ≤ n. Permutacje P i Q są prawie takie same jeśli istnieje sekwencja rotacji okien, która się przekształca P w Q. Prawie równość jest relacją równoważności. Oto deklarowana charakterystyka klas równoważności.

(1) m = 1: P almost equals Q if and only if P = Q
(2) m = n: P almost equals Q if and only if they"re rotations of each other
(3) 1 < m < n, m odd: P almost equals Q if and only if they have the same parity
(4) 1 < m < n, n even: P almost equals Q

Pierwsze dwa twierdzenia są oczywiste. Co się tyczy (3), konieczność warunku parzystości wynika z faktu, że obracanie okna o długości nieparzystej jest równą permutacją.

Istotą tego argumentu jest znalezienie algorytmu, kiedy n = m + 1 ≥ 4, ponieważ ogólnie możemy użyć algorytmu podobnego do rodzaju wstawiania, aby przekształcić P tak, że wszystko oprócz ostatniego m + 1 dopasowanie elementów Q, a konkretnie sprawa (n, m) = (3, 2) można rozwiązać przez kontrolę. W razie gdyby m jest nawet, zapewniamy dalej, że transformacja odpowiada parzystości Q, obracając ostatni m elementy w razie potrzeby. (Dla m dziwne, przyjmujemy tylko równe parytety.)

Potrzebujemy techniki przenoszenia mniejszej niż m elementy naraz. Załóżmy, że stan jest następujący.

1, 2, 3, 4, ..., m, m + 1

Obróć drugie okno m - 1 razy (tj. raz na odwrót).

1, 3, 4, ..., m, m + 1, 2

Obróć pierwsze okno m - 1 czasy.

3, 4, ..., m, m + 1, 1, 2

Po drugie, dwa razy.

3, 2, 4, ..., m, m + 1, 1
3, 1, 2, 4, ..., m, m + 1

Udało nam się obrócić pierwsze trzy elementy. To wystarcza w połączeniu z koniugacją przez rotacje do „wstawiania” pierwszego m - 1 elementy Q do miejsca. Pozostałe dwa są w odpowiedniej kolejności według dopasowania parzystości.

---