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 sir de caractere de lungime N, indexat de la 0. Sirul de caractere S(i, j) este sirul de caractere de lungime 2^j ce se termina pe pozitia i, daca el exista. Functia brperm(i, j) este 1 daca S(i, j) exista si 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, iar pe al doilea rand sirul de caractere dat.

Date de ieşire

În fişierul de ieşire brperm.out se afiseaza suma din brperm(i, j) * 2^{20i + j} pentru i de la 0 la N - 1 si j de la 0 la 19.

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?