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

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 ≤ 2.000.000.000$

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

h2. Exemplu

| 5
| 5
|

| 6
| 8

| 2707124
| 660634

|

h3. Indicatii pentru rezolvare
 
O implementare directa a relatiei de recurenta ar trebui sa obtina 20 de puncte si se gaseste 'aici':/.
 
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:

h2. Indicaţii de rezolvare

<tex>\[ \left( \begin{array}{cccc}F_K_ & F_K + 1_ & -7 & 0 \\9 & 2 & -6 & 2 \\-4 & 1 & -4 & 1 \\-1 & 8 & 0 & -2 \end{array} \right)\]</tex>

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.
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>:
<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
 
* '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