Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ccount.in, ccount.out | Sursă | ad-hoc |
| Autor | Mihai Calancea | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Ccount
Fie urmatorul sir:
A(1) = 1.
A(2) = 3.
A(i) = x * A(i - 1) + y * A(i - 2), pentru orice i mai mare sau egal cu 3.
Se da o lista de pozitii P1, P2.. Pk, cu semnificatia ca valorile A(P1), A(P2), ... A(Pk) sunt cunoscute. Se considera ca valorile A(1) si A(2) sunt de-asemenea cunoscute, chiar daca numerele 1 si 2 s-ar putea sa nu fie incluse in lista P.
Procedura de calcul pentru un anumit termen al sirului, fie el A(n) este urmatoarea:
1. Daca A(n) este cunoscut, finalizam procedura.
2. Daca A(n - 1) nu este cunoscut, vom aplica procedura de calcul pentru A(n - 1).
3. Daca A(n - 2) nu este cunoscut, vom aplica procedura de calcul pentru A(n - 2).
4. Aplicam relatia sirului: A(n) = x * A(i - 1) + y * A(i - 2).
Cate proceduri de calcul vor fi realizate pentru a calcula valoarea lui A(n)?
Deoarece acest numar poate fi foarte mare, rezultatul se va afisa modulo 9007.
Date de intrare
Fişierul de intrare ccount.in va contine pe prima sa linie numarul N si numarul K, reprezentand indicele termenului pentru care oferim raspunsul, respectiv numarul de elemente al listei P.
Cea de a doua linie va contine K numere, reprezentand lista P.
Date de ieşire
În fişierul de ieşire ccount.out se va afla raspunsul problemei modulo 9007.
Restricţii
- 1≤ N ≤ 10^5%
- A modulo B se refera la restul impartirii numarului A la numarul B.
Urmatoarele relatii sunt valabile si pot fi necesare pentru a calcula rezultatul fara a depasi tipurile de date C++:
(A + B) modulo C = (A modulo C + B modulo C) modulo C
(A * B) modulo C = ((A modulo C) * (B modulo C)) modulo C
Exemplu
| ccount.in | ccount.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
