h2. 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$.

Poveste şi cerinţă...

Am considerat ca sunt date anumite queryuri in input, daca secventa cutare e sau nu br-palindrom. Desigur, putem schimba formatul asta in varianta originala, in caz ca devine inutila schimbarea.

$A{~i~} = X{~i~} mod N$
$B{~i~} = Y{~i~} mod log{~2~}(lungimea lantului de la A{~i~} la radacina)$

$R{~i~} = brperm(A{~i~}, B{~i~})$

$R{~i~} = 1 daca lantul de lungime $2^B{~i~}^$ de la $A{~i~}$ insrep radacina este br-permutare, 0 altfel$.

$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$