Fişierul intrare/ieşire:melodii.in, melodii.outSursăFMI No Stress 4
AutorAndrei Cristian LambruAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 km sau exista un i astfel incat a i ≠ b i.
  • R nu este neaparat un numar prim

Exemplu

melodii.inmelodii.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content