Pagini recente » Borderou de evaluare (job #693818) | Borderou de evaluare (job #473886) | Borderou de evaluare (job #1665231) | Borderou de evaluare (job #1661381) | Al k-lea termen Fibonacci

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

Fişierul intrare/ieşire:	kfib.in, kfib.out	Sursă	Arhiva Educationala
Autor	Arhiva Educationala	Adăugată de	Cezar Mocan •CezarMocan
Timp execuţie pe test	0.025 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

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.in	kfib.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 M_i 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 $M_{i}$ este egal cu $Z \times M_{i-1}$ si mai stim ca $M_{i-1}$ este egal cu $Z \times M_{i-2}$ . Din proprietatea de asociativitate a inmultirii matricilor rezulta ca $M_{i}$ este egal cu $Z^2 \times M_{i-2}$ . Inductiv rezulta ca $M_{i}$ = $Z^{N-1} \times M_{1}$ . 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.