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) = 1.
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:

intreg F(intreg n) {
  daca A(n) este cunoscut atunci intoarce valoarea A(n); 
  calcule_totale++;  
  intoarce valoarea F(n - 1) + F(n - 2);
}

Care va fi valoarea variabilei globale calcule_totale dupa ce apelam F(n)?
Deoarece acest numar poate fi foarte mare, rezultatul se va afisa mod 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 mod 9007.

Restricţii

• 1 ≤ N ≤ 10⁵
• A mod B se refera la restul impartirii numarului A la numarul B.
• Dupa apelarea functiei F(n), valoarea A(n) nu devine cunoscuta in continuare. Astfel, F(n) va fi apelata de oricate ori este nevoie pentru o anumita valoare a lui n.
• Urmatoarele relatii sunt valabile si pot fi necesare pentru a calcula rezultatul fara a depasi tipurile de date C++:
• (A + B) mod C = (A mod C + B mod C) mod C
• (A * B) mod C = ((A mod C) * (B mod C)) mod C

Exemplu

Explicaţie

Variabila calcule_totale este incrementata in apelurile F(6), F(4), F(3).
Observati ca daca A(5) nu ar fi fost cunoscut, raspunsul ar fi fost 7.

Cum se trimit solutii?