Fişierul intrare/ieşire:	brperm.in, brperm.out	Sursă	RMI 2020 Ziua 1
Autor	Tamio-Vesa Nakajima	Adăugată de	Mihai-Cristian Popescu •mihai50000
Timp execuţie pe test	1 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Brperm

Editorialul

SE DA UN ARBORE...

Consideram permutare BR: bit reverse.
Un sir de lungime 2^k este BR-permutare daca si numai daca este egal cu el insusi dupa ce se aplica BR.
Se da un arbore cu N noduri, indexate de la 0, cu caractere pe muchii. Sirul de caractere S(i, j) este sirul de caractere de lungime 2^j format prin concatenarea caracterelor de pe lantul de acea lungime de la i inspre radacina. Functia brperm(i, j) este 1 daca S(i, j) este BR-permutare, iar 0 altfel. In aceasta problema se cere sa calculati eficient functia brperm.

Date de intrare

Fişierul de intrare brperm.in contine pe primul rand numarul N de noduri.
Al doilea rand contine cate N - 1 numere, iar al i-lea este tatal nodului i in arbore (retineti ca nodul 0 este radacina). Se garanteaza ca tatal unui nod are indicele mai mic ca el.
Al treilea rand contine un sir de N - 1 caractere, din care al i-lea caracter este caracterul pe muchia dintre i si tatal sau.
Al patrulea rand contine valorile Q X₁ Y₁ a b c d.

Date de ieşire

În fişierul de ieşire brperm.out se afiseaza numerele X_Q+1 Y_Q+1. Acestea se definesc dupa recurentele urmatoare:

A_i = X_i mod N
B_i = Y_i mod log₂(lungimea lantului de la A_i la radacina)
R_i = brperm(A_i, B_i)
X_i+1 = (i + X_i + R_i) * a + b mod 1.000.000.007
Y_i+1 = (i + Y_i + R_i) * c + d mod 1.000.000.007

Restricţii

• SIGMA = 26

• ... ≤ ... ≤ ...

• Subtask1 (10 puncte): O(Q * N * logN) && NU neaparat linie
• Subtask2 (10 puncte): O(N * logN + Q * N) && NU neaparat linie
• Subtask3 (10 puncte): O(N * logN + Q) && linie && SIGMA = 2 && biased random (comisia a ales, pt fiecare test, cate un numar real p intre 0 si 1 iar fiecare caracter este 'a' cu probabilitate p si 'b' cu probabilitate 1-p)
• Subtask4 (30 puncte): O((N + Q) * logN * logN) sau O((N + Q) * sqrt(N + Q) + Q) (nu cunosc solutie, dar cine stie?) - anulat si inghitit de subtaskul urmator in caz ca nu dam queryuri
• Subtask5 (10 puncte): O(N * logN * logN + Q) - acelasi lucru ca subtaskul urmator daca nu dam queryuri
• Subtask6 (10 puncte): O((N + Q) * logN) - in caz ca exista
• Subtask7 (20 puncte): O(N * logN + Q) - in caz ca exista, altfel punctele merg la ultimul subtask existent

Exemplu

Explicaţie

...

Cum se trimit solutii?