Al K-lea termen Fibonacci

Al k-lea termen Fibonacci

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

Se da sirul lui Fibonacci, $F{~1~} = 1$, $F{~2~} = 1$, ... $F{~i~} = F{~i - 1~} + F{~i - 2~}$. Sa se calculeze al $N$-lea termen al sirului $modulo 666013$.

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>.
 
h2. Cerinţă
 
Să se calculeze al $K$-lea termen al şirului modulo $666013$.

h2. Date de intrare

Fişierul de intrare $kfib.in$ se gaseste un numar natural $N$.

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

h2. Date de ieşire

În fişierul de ieşire $kfib.out$ se va afisa al $N$-lea termen al sirului $modulo 666013$.

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

h2. Restricţii

* $3 ≤ N ≤ 1.000.000.000$

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

h2. Exemplu

| 8
|

h3. Indicatii pentru rezolvare

*Marius*: Nu ar merge al doilea exemplu să fie K un milion şi ceva?
 
h3. Indicaţii pentru rezolvare

O implementare directa a relatiei de recurenta ar trebui sa obtina 20 de puncte si se gaseste 'aici':/job_detail/372678?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 obtine 100 de puncte trebuie gasita o metoda mai eficienta de a rezolva aceasta recurenta. Ne vom folosi de 'inmultirea matricilor':http://en.wikipedia.org/wiki/Matrix_multiplication#Ordinary_matrix_product in felul urmator: la pasul $K$ o sa avem deja calculate $F{~K - 2~}$ si $F{~K - 1~}$ si vrem sa il aflam pe $F{~K~}$.

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_K - 2_ & F_K - 1_ \end{array} \right)\] & \times </tex>  <tex>

\[\left( \begin{array}{ccc}
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_K - 1_ & F_K_ \end{array} \right)\] </tex>

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

Vom nota cu $M{~i~}$ matricea <tex>
\emph{}
\[ \left( \begin{array}{ccc}

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

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

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

'Solutia':/job_detail/372680?action=view-source foloseste 'ridicarea la putere in timp logaritmic':/problema/lgput.

'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? :)

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