Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | kfib.in, kfib.out | Sursă | Arhiva Educationala |
Autor | Arhiva Educationala | Adăugată de | Cezar Mocan •CezarMocan |
Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Al k-lea termen Fibonacci
Fie şirul lui Fibonacci, dat prin .
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
- 1 ≤ K ≤ 1 000 000 000.
Exemplu
kfib.in | kfib.out |
---|---|
5 | 5 |
2707124 | 660634 |
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.
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 în felul următor: la pasul vom avea deja calculate şi şi vrem să îl aflăm pe :
Vom nota cu Mi matricea iar cu Z matricea constantă, .
Stim ca este egal cu si mai stim ca este egal cu . Din proprietatea de asociativitate a inmultirii matricilor rezulta ca este egal cu . Inductiv rezulta ca = . Soluţia optima se foloseşte de ridicarea la putere în timp logaritmic, avand complexitatea finala de . este numarul de operatii efectuate la fiecare pas al ridicarii la putere si este egal cu dimensiunea matricii constante la puterea a -a, adica .
Aplicaţii
- Iepuri
- Hprob
- Nice Patterns Strike Back, SGU
- Tour Counting, Topcoder
- Ecu
- Pkinv
- Recurenta2
- Nr2