h2. Subtaskul 4, $36$ puncte

Notăm cu $d{~T~}(x, y)$ (distanţă în $T$ de la $x$ la $y$) că numărul de ori necesar de a aplica $x = T[x]$ până când $x$ devine egal cu $y$. Dacă asta este imposibil, $d{~T~}(x, y) = -1$.

Notăm cu $d{~T~}(x, y)$ (distanţă în $T$ de la $x$ la $y$) că numărul de ori necesar de a aplică $x = T[x]$ până când $x$ devine egal cu $y$. Dacă asta este imposibil, $d{~T~}(x, y) = -1$.

Să descompunem cele două permutări în cicluri.
Observaţie^({$1$})^: în ziua $x$, cei doi se vor întâlni în $y$ dacă şi numai dacă $x$ şi $y$ aparţîn aceluiaşi ciclu şi în $A$, şi în $B$.
Reformulare^({$2$})^: Dacă în fiecare ciclu am desemna un reprezentant (aleator), iar pentru fiecare valoare $x$ din ciclul respectiv am notă distanţă acestuia de la reprezentant cu $D_A{~x~}$ pentru permutarea $A$, respectiv $D_B{~x~}$ pentru permutarea $B$, iar cu $L_A{~x~}$ şi $L_B{~x~}$ lungimea ciclului căruia aparţine $x$ în $A$, respectiv în $B$, atunci în ziua $x$ cei doi se văd în $y$ dacă şi numai dacă aparţîn aceluiaşi ciclu în ambele permutări, şi $(D_A{~y~} - D_A{~x~}) mod L_A{~x~} = (D_B{~y~} - D_B{~x~}) mod L_B{~x~}$

Cum pentru toate numerele $L_A{~x~} = L_B{~x~} = N$, putem asocia fiecărei valori câte un coeficient $C{~x~} = (D_A{~x~} - D_B{~x~}) mod N$. Pentru fiecare $x$, numărul de $y$ unde cei doi se vor întâlni este egal cu numărul de valori $y$ a.i. $C{~x~} = C{~y~}$ cum $(D_A{~x~} - D_B{~x~}) mod N = (D_A{~y~} - D_B{~y~}) mod N <=> (D_A{~y~} - D_A{~x~}) mod N = (D_B{~y~} - D_B{~x~}) mod N$, iar din din ^({$2$})^ aceasta este corect. Se poate utiliza un vector de frecvenţa pentru calcularea numărului de valori $y$ care au $C{~y~} = C$, $C$ fiind variabil după $x$. Complexitate timp (şi memorie): $O(N)$

Cum pentru toate numerele $L_A{~x~} = L_B{~x~} = N$, putem asocia fiecărei valori câte un coeficient $C{~x~} = (D_A{~x~} - D_B{~x~}) mod N$. Pentru fiecare $x$, numărul de $y$ unde cei doi se vor întâlni este egal cu numărul de valori $y$ a.i. $C{~x~} = C{~y~}$ cum $(D_A{~x~} - D_B{~x~}) mod N = (D_A{~y~} - D_B{~y~}) mod N <=> (D_A{~y~} - D_A{~x~}) mod N = (D_B{~y~} - D_B{~x~}) mod N$, iar din din ^({$2$})^ această este corect. Se poate utiliza un vector de frecvenţa pentru calcularea numărului de valori $y$ care au $C{~y~} = C$, $C$ fiind variabil după $x$. Complexitate timp (şi memorie): $O(N)$

Motivul pentru care o asemenea soluţie nu funcţionează pe cazul general este datorit inabilităţii de a pune valorile care depind de $x$ respectiv $y$ de aceeaşi parte a parantezei aşa cum este formulat în ^({$2$})^, cum cele două părţi ale egalităţii se pot afla sub modulo-uri diferite. Încercări de a lucra peste mulţimea valorilor $y$ care sunt în acelaşi ciclu că $x$ şi pentru care se fixează o ierarhie între valorile din diferenţe (adică $y$ să respecte că $D_A{~x~} < D_A{~y~}$, $D_B{~x~} < D_B{~y~}$, şi restul de combinaţii de semne), astfel încât ecuaţia de la ^({$2$})^ să aibă ambele părţi ale egalităţii ca ecuaţii în $Z$ pot duce la o soluţie în $O(N * log(N))$ care ar putea trece pe Subtaskul 5.

Motivul pentru care o asemenea soluţie nu funcţionează pe cazul general este datorit inabilităţii de a pune valorile care depind de $x$ respectiv $y$ de aceeaşi parte a parantezei aşa cum este formulat în ^({$2$})^, cum cele două părţi ale egalităţii se pot află sub modulo-uri diferite. Încercări de a lucra peste mulţimea valorilor $y$ care sunt în acelaşi ciclu că $x$ şi pentru care se fixează o ierarhie între valorile din diferenţe (adică $y$ să respecte că $D_A{~x~} < D_A{~y~}$, $D_B{~x~} < D_B{~y~}$, şi restul de combinaţii de semne), astfel încât ecuaţia de la ^({$2$})^ să aibe ambele părţi ale egalităţii că ecuaţii în $Z$ pot duce la o soluţie în $O(N * log(N))$ care ar putea trece pe Subtaskul 5.

h2. Subtaskul 6, $100$ puncte