== include(page="template/taskheader" task_id="kfib") ==

Fie 'şirul lui Fibonacci':http://en.wikipedia.org/wiki/Fibonacci_number, dat prin <tex> F_{1} = 1, F_{2} = 1, \ldots, F_{n} = F_{n-1} + F_{n-2} </tex>.

Fie 'şirul lui Fibonacci':http://en.wikipedia.org/wiki/Fibonacci_number dat prin recurenţa <tex> F_{0} = 0, F_{1} = 1, \ldots, F_{n} = F_{n-1} + F_{n-2} </tex>.

h2. Cerinţă

h2. Restricţii

* $1 ≤ K ≤ 1 000 000 000$.

* $0 ≤ K ≤ 1 000 000 000$.

h2. Exemplu

| 5
| 5
|

| 6
| 8

| 2707124
| 660634

|

*Marius*: Nu ar merge al doilea exemplu să fie K un milion şi ceva?

h2. Indicaţii de rezolvare

h3. 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':job_detail/382677?action=view-source.

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':/job_detail/372678?action=view-source.

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':http://en.wikipedia.org/wiki/Matrix_multiplication#Ordinary_matrix_product în felul următor: la pasul <tex> n </tex> vom avea deja calculate <tex> F_{n-2} </tex> şi <tex> F_{n-1} </tex> şi vom dori să îl aflăm pe <tex> F_{n} </tex>:

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':http://en.wikipedia.org/wiki/Matrix_multiplication#Ordinary_matrix_product în felul următor: la pasul $n$ vom avea deja calculate <tex> F_{n-2} </tex> şi <tex> F_{n-1} </tex> şi vrem să îl aflăm pe <tex> F_{n} </tex>:

<tex>
\emph{}
\[\left( \begin{array}{ccc}

F_n-2_ & F_n-1_ \end{array} \right)\] & \times </tex>  <tex>

F_{n-2}_ & F_{n-1}_ \end{array} \right)\] & \times </tex>  <tex>

\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)\] </tex>

F_{n-1}_ & F_n_ \end{array} \right)\] </tex>

Vom nota cu $M{~i~}$ matricea <tex>

Vom nota cu <tex> M_{i} </tex> matricea <tex>

\emph{}
\[ \left( \begin{array}{ccc}

F_i-1_ & F_i_ \end{array} \right)\] </tex> iar cu $Z$ matricea constantă, <tex> \emph{}

F_{i-1}_ & F_i_ \end{array} \right)\] </tex> iar cu <tex> Z </tex> matricea constantă <tex> \emph{}

\[ \left( \begin{array}{ccc}
0 & 1 \\
1 & 1 \end{array} \right)\] </tex>.

'Soluţia':/job_detail/372680?action=view-source foloseşte 'ridicarea la putere în timp logaritmic':/problema/lgput.
 
*Marius*: Cum se ajunge la ridicare în timp logaritmic? :)

Ştim că <tex>M_{i} = M_{i-1} \times Z </tex> şi mai ştim că <tex>M_{i-1} = M_{i-2} \times Z </tex>. Din proprietatea de asociativitate a înmulţirii matricelor rezultă că <tex>M_{i} = M_{i-2} \times Z^2 </tex>. Inductiv, rezultă egalitatea <tex>M_{i} = M_{1} \times Z^{i-1}</tex>. 'Soluţia':job_detail/382679?action=view-source optimă se foloseşte de 'ridicarea la putere în timp logaritmic':/problema/lgput, având complexitatea <tex>O(log K)</tex>. 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 <tex> Z </tex> la puterea a <tex>3</tex>-a, care este <tex>8</tex>.

h2. Aplicaţii

# 'Iepuri':problema/iepuri
# 'Hprob':problema/hprob
# "Nice Patterns Strike Back":http://acm.sgu.ru/problem.php?contest=0&problem=197, _SGU_
# "Tour Counting":http://www.topcoder.com/stat?c=problem_statement&pm=6386, _Topcoder_
# 'Ecu':problema/ecu
# 'Pkinv':problema/pkinv
# 'Recurenta2':problema/recurenta2
# 'Nr2':problema/nr2

* 'Iepuri':problema/iepuri
* 'Hprob':problema/hprob
* 'Ecu':problema/ecu
* 'Pkinv':problema/pkinv
* 'Recurenta2':problema/recurenta2
* 'Nr2':problema/nr2
* "Nice Patterns Strike Back":http://acm.sgu.ru/problem.php?contest=0&problem=197, _SGU_
* "Tour Counting":http://www.topcoder.com/stat?c=problem_statement&pm=6386, _Topcoder_

== include(page="template/taskfooter" task_id="kfib") ==

4411