Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-01-04 15:55:00.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:kfib.in, kfib.outSursăArhiva Educationala
AutorArhiva EducationalaAdăugată deCezarMocanCezar Mocan CezarMocan
Timp execuţie pe test0.025 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Al k-lea termen Fibonacci

Fie şirul lui Fibonacci, dat prin  F_{1} = 1, F_{2} = 1, \ldots, F_{n} = F_{n-1} + F_{n-2} .

Cerinţă

Să se calculeze al K-lea termen al şirului modulo 666013.

Date de intrare

Fişierul de intrare kfib.in conţine o singură linie cu numărul natural K.

Date de ieşire

În fişierul de ieşire kfib.out se va afişa al K-lea termen al şirului modulo 666013.

Restricţii

  • 1 ≤ K ≤ 1 000 000 000.

Exemplu

kfib.inkfib.out
5
5
2707124
660634

Indicaţii pentru rezolvare

O implementare directă a relaţiei de recurenţă în complexitate liniară ar trebui să obţină 20 de puncte şi se găseşte aici.

Pentru a obţine 100 de puncte trebuie găsită o metoda mai eficientă de a rezolva această recurenţă. Ne vom folosi de înmulţirea matricilor în felul următor: la pasul n vom avea deja calculate  F_{n-2} şi  F_{n-1} şi vrem să îl aflăm pe  F_{n} :

\emph{}
\[\left( \begin{array}{ccc}
F_n-2_ & F_n-1_ \end{array} \right)\] & \times 
\emph{}
\[ \left( \begin{array}{ccc}
0 & 1 \
1 & 1 \end{array} \right)\] =  \emph{}
\[ \left( \begin{array}{ccc}
F_n-1_ & F_n_ \end{array} \right)\]

Vom nota cu Mi matricea 
\emph{}
\[ \left( \begin{array}{ccc}
F_i-1_ & F_i_ \end{array} \right)\] iar cu Z matricea constantă,  \emph{}
\[ \left( \begin{array}{ccc}
0 & 1 \
1 & 1 \end{array} \right)\] .

Stim ca Mi este egal cu Z * Mi-1 si mai stim ca Mi-1 este egal cu Z * Mi-2. Din proprietatea de asociativitate a inmultirii matricilor rezulta ca Mi este egal cu Z2 * Mi-2. Inductiv rezulta ca Mi = ZN-1 * M1. Soluţia optima se foloseşte de ridicarea la putere în timp logaritmic, avand complexitatea finala de O(log K * CONST). CONST este numarul de operatii efectuate la fiecare pas al ridicarii la putere si este egal cu dimensiunea matricii constante la puterea a 3-a, adica 8.

Aplicaţii

  1. Iepuri
  2. Hprob
  3. Nice Patterns Strike Back, SGU
  4. Tour Counting, Topcoder
  5. Ecu
  6. Pkinv
  7. Recurenta2
  8. Nr2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?