Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Al k-lea termen Fibonacci

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 recurenţa $F_{0} = 0, F_{1} = 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

0 ≤ K ≤ 1 000 000 000.

Exemplu

kfib.in	kfib.out
5	5
2707124	660634

Indicaţii de 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 metodă eficientă de a rezolva această recurenţă. Ne vom folosi de înmulţirea matricelor în felul următor: la pasul $n$ vom avea deja calculate $F_{n-2}$ şi $F_{n-1}$ şi vom dori 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)\]$ .

Ştim că $M_{i} = M_{i-1} \times Z$ şi mai ştim că $M_{i-1} = M_{i-2} \times Z$ . Din proprietatea de asociativitate a înmulţirii matricelor rezultă că $M_{i} = M_{i-2} \times Z^2$ . Inductiv, rezultă egalitatea $M_{i} = M_{1} \times Z^{i-1}$ . Soluţia optimă se foloseşte de ridicarea la putere în timp logaritmic, având complexitatea $O(log K)$ . Constanta ce se ascunde în spatele acestei complexităţi este egală cu numărul de operaţii efectuate la fiecare pas al ridicării la putere, adică cu dimensiunea matricii constante $Z$ la puterea a $3$ -a, care este $8$ .