Al k-lea termen Fibonacci

Al K-lea termen Fibonacci

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

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

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

h2. Date de intrare

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

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

h2. Date de ieşire

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

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

h2. Restricţii

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

* $3 ≤ N ≤ 2.000.000.000$

h2. Exemplu

| 5
| 5
|

| 2707124
| 660634

| 6
| 8

|

h2. Indicaţii de rezolvare

h3. Indicatii 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 directa a relatiei de recurenta ar trebui sa obtina 20 de puncte si se gaseste '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':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 obtine 100 de puncte trebuie gasita o metoda mai eficienta de a rezolva aceasta recurenta, lucru realizabil prin transpunerea ei in matrici in felul urmator:

<tex>
\emph{}

\[\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_{n-1}_ & F_n_ \end{array} \right)\] </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 <tex> Z </tex> matricea constantă <tex> \emph{}

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

0 & 1 \\
1 & 1 \end{array} \right)\] </tex>.
 
Ş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

a & b \\
1 & 0 \end{array} \right)\] </tex>

* '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_

**Nu imi merge sa fac matricile in latex, imi da eroarea asta:" Warning: Cannot modify header information - headers already sent by (output started at /home/infoarena/live/www/views/header.php:98) in /home/infoarena/live/common/log.php on line 309 "**
*bogdan2412*: Ramasesem fara spatiu pe disc iara :P

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

4411