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

Vezi solutiile trimise | Statistici

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.inkfib.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.

Aplicaţii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content