Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | melodii.in, melodii.out | Sursă | FMI No Stress 4 |
| Autor | Andrei Cristian Lambru | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Melodii
Alinut a fost invitat la aniversarea prietenei lui dragi, Alinuta, pe post de DJ. Cu 5 minute inainte de a da drumul la mixer si-a dat seama ca in realitate el nu cunoaste decat 2 melodii (prima dureaza 1 minut, iar a doua 2 minute), dar a fost chemat pentru exact N minute de spectacol. Deoarece Alinut este student la FMI si nu la Conservator si in plus nu prea mai are timp la dispozitie, acest lucru nu il deranjeaza prea mult, dar este curios sa stie pentru cele N minute de reprezentatii care este numarul de moduri diferite de a dispune cele 2 melodii astfel incat reprezentatia sa dureze exact cele N minute. De exemplu pentru N = 4 minute, el are la dispozitie 5 posibilitati de dispunere a melodiilor : 1, 1, 1, 1 ; 1, 1, 2 ; 1, 2, 1 ; 2, 1, 1 ; 2, 2.
Dupa ce a calculat pentru N ≤ 100 (cu backtracking) si-a dat seama ca acest numar este destul de mare, asa ca doreste sa afle doar restul impartirii acestui numar la R, numarul lui norocos. In plus el doreste raspunsul la aceasta intrebare pentru T valori diferite ale lui N.
Date de intrare
Pe prima linie a fişierului de intrare melodii.in se vor gasi valorile T si R cu semnificatia de mai sus.
Pe fiecare din urmatoarele T linii se va afla exact o singura valoare ce va semnifica numarul N de minute pentru testul respectiv.
Date de ieşire
În fişierul de ieşire melodii.out se vor afisa exact T linii. Pe a i-a linie se va afla raspunsul pentru a i-a intrebare din fisierul de intrare.
Restricţii
- 1 ≤ T ≤ 100 000
- 3 ≤ R ≤ 100 000
- 1 ≤ N ≤ 1018
- Pentru 50% din teste, 1 ≤ N ≤ 1 000 000
- Doua subsecvente de melodii a 1, a 2, ... a k si b 1, b 2, ... b m se considera distincte, daca k ≠ m sau exista un i astfel incat a i ≠ b i.
- R nu este neaparat un numar prim
Exemplu
| melodii.in | melodii.out |
|---|---|
| 5 5 1 2 3 10 666013 | 1 2 3 4 2 |
Explicaţie
Pentru N = 1 se poate reda doar melodia care dureaza 1 minut.
Pentru N = 2 sunt 2 moduri de dispunere a melodiilor : 1, 1 ; 2.
Pentru N = 3 sunt 3 moduri: 1, 1 , 1 ; 2, 1 ; 1, 2.
Pentru N = 10 sunt 89 de moduri, iar raspunsul este 89 modulo 5 = 4.
