Revizia anterioară Revizia următoare
| 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
SE DA UN ARBORE...
Notă: În enunţ, b1...bk reprezintă un întreg scris în notaţie binară, unde b1 este cel mai semnificativ bit, iar bk este cel mai puţin semnificativ bit.
Vrăjitoarea Roxana, în timp ce zbura pe mătură prin galaxie, a descoperit o nouă planetă (paneta BR-PERM) unde toţi locuitorii erau implicaţi într-un dans ciudat. În acest dans, participanţii stau într-o linie, iar apoi se reordonează. Într-un dans la care participa 2k locuitori, persoana de pe poziţia b1...bk se va muta la poziţia bk...b1 (indexat de la 0).
Roxana a realizat că fiecare persoana de pe BR-PERM poartă îmbrăcaminte din una dintre cele 26 de culori. Aceste culori vor fi reprezentate de litere din alfabetul Latin.
BR-PERM-ienii consideră speciale şirurile de dansatori unde secvenţa de culori pe care locuitorii le poarta înainte şi după dans sunt la fel. Ei numesc astfel de secvenţe drăguţe. De exemplu, cand k=2, avem un şir de 4 dansatori 0, 1, 2, 3 care dupa dans va fi ordonat în următorul fel: 0, 2, 1, 3. Astfel secvenţa de culori abbaeste drăguţă, dar abca nu este.
BR-PERM-ienii o roagă pe Roxana să îi ajute cu această problemă (se pare că vrăjitoarele mereu ajută oamenii să îşi rezolve problemele. Aceştia îi arată un şir de n dansatori şi o roagă să îi răspundă la mai multe întrebari: "Este secvenţa de lungime 2k care începe la dansatorul i drăguţă?
Date de intrare
Fişierul de intrare brperm.in contine un rand, cu sirul de caractere dat.
Date de ieşire
Definim R(x) ca suma din brperm(i, j) * x20i + j mod 1.000.000.007 pentru i de la 0 la N - 1 si j de la 0 la 19.
În fişierul de ieşire brperm.out se afiseaza R(2). Daca ne e frica bagam si R(3) R(5)
Restricţii
- 1 ≤ N ≤ 500000
- 1 ≤ Q ≤ 500000
Punctare
Subtask 1 (
Exemplu
| brperm.in | brperm.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
