Avem foarte mult timp la dispozitie. Nu ne permitem ca pentru un query q sa pornim de la t=0 si sa urmam recurenta pana la t=q. Ce ne permitem in schimb este sa calculam la inceput valorile pana la pasul 10^7^ si sa retinem doar in anumite locuri rezultatul. Putem sa pornim cautarea atunci de la cel mai apropiat punct inainte de q. Vom retine evident rezultatul la puncte echidistante. Daca retinem rezultatul din <tex>{\sqrt{M}}</tex> in <tex>{\sqrt{M}}</tex> producem o balansare intre timp si memorie. Complexitatea finala va fi <tex>O(M + Q*{\sqrt{M}})</tex> ca timp si <tex>O({\sqrt{M}})</tex> ca memorie. Limita de memorie ne permite si mai mult. Cu cat gap-ul dintre punctele precalculate este mai mic, cu atat solutia va fi mai rapida.

==include(page="onis-2015/solutii-runda-1/semipal")==

==include(page="onis-2015/solutii-runda-1/semipal")==
 
Sa distilam ce inseamna un semiplaindrom. Ca un cuvant sa fie semipalindrom este necesar si suficient ca ultima litera sa fie egala cu prima. Atunci numarul de semipalindroame de lungime N formate din 'a' si 'b' este 2^N-1^ - deci K se va incadra in tipul @long long@. Configuratia binara a lui K va dicta primele N-1 litere din sir (1 inseamna 'b' si 0 inseamna 'a') iar ultima litera este unic determinata de prima. Vedeti ? Nu-i asa greu la Petrozaporksk.