044 Al k-lea termen Fibonacci

[•Marius]

Aici puteţi discuta despre problema Al k-lea termen Fibonacci.

[•Robytzza]

cine imi explica si mie de ce sursa asta ia 100-a :
http://infoarena.ro/job_detail/380187?action=view-source

Cod:

#include<fstream>
using namespace std;
int main()
{
fstream in("kfib.in",ios::in),out("kfib.out",ios::out);
    int x=0,y=1,z,k;
    in>>k;
    while(k--%1332028)z=(x+y)%666013,x=y,y=z;
    out<<x<<endl;
}

aha ms

[•klamathix]

Numerele Fibonacci sunt periodice modulo m . Cel mai probabil 1332028 este lungimea perioadei pentru m = 666013.

[•yo_s_canta]

Exista formula pentru termenul general la sirul fibonacci (nu ma refer la recurenta)
O explicatie : http://www.ginfo.ro/revista/14_1/mate2.pdf

[•Cosmin]

Nu prea ai ce face cu formula pt problema asta pt ca ti-ar trebui calcule cu numere reale de precizie mare.

[•SpiderMan]

Nu cred ca merge cu numere mari

[•yo_s_canta]

N-am incercat sa implementez... dar banuiesc ca daca folosesti round() o sa dea bine

[•Cosmin]

Ia incearca, ca sa intelegi mai bine ce se intampla.

[•otilia_s]

Puteti sa imi explicati si mie va rog cum functioneaza "1LL" din expresia:
         C[j] = (C[j] + 1LL * A[k] * B[k][j]) % mod;
Presupun ca transforma in long long, pentru cazul in care A[k]*B[k][j] depaseste tipul int. Dar mi-ar placea sa inteleg mai bine ce se intampla cu expresia si in ce context ar mai putea fi folosit. 
Multumesc! 

[•wefgef]

1LL înseamna valoarea 1 reținută pe 64 de biți. Când înmulțești un long long cu un int, se va face cast la long long. Astfel, dacă vrei să înmulțești două variabile A și B de tip int, iar produsul lor intră doar pe long long, poți face ca mai sus: 1LL * A  * B. O altă varianta ar fi să scrii tu castul de mână: (long long)(A) * B.

[•otilia_s]

Am inteles!  Multumesc!

[•S7012MY]

Ar mai fi aici si problema nkbiti

[•caen1]

Exista vreun mod prin care sa determini (rapid) perioada in astfel de cazuri, sau metoda simpla nu este practica in timpul unui concurs? Multumesc!

[•scipianus]

Cred ca este o problema cu timpii la evaluator la problema aceasta,intrucat observ in monitor foarte multe surse de 0.30-0.50kb care implementeaza fibonacci in mod clasic,liniar,surse care iau 100pct,desi se zice ca ar trebui sa ia vreo 20pct 

[•klamathix]

Cred ca este o problema cu timpii la evaluator la problema aceasta,intrucat observ in monitor foarte multe surse de 0.30-0.50kb care implementeaza fibonacci in mod clasic,liniar,surse care iau 100pct,desi se zice ca ar trebui sa ia vreo 20pct 

Mnop. Sursele alea se folosesc de periodicitatea numerelor Fibonacci modulo n. Pentru n-ul din problema asta, perioada e mica (2 * n parca ) si poate fi calculata liniar.

[•NicuCJ]

Merge cu o idee asemanatoare sa faci in timp logaritmic si al k-lea termen fibonacci de 3, 4, 5 s.a.m.d. ?(fib de 3 fiind Fn=Fn-1+Fn-2+Fn-3)

[•pauldb]

Da.

[•NicuCJ]

Imi poti spune te rog cum arata matricea fixata pentru fib de 3? Nu gasesc niciun pattern fata de fib de 2.

[•klamathix]

Iti spunem duminica la 00:00:00 daca vrei .

L.E: Sarumana, Craciun .

[•deneo]

@Mihai
Cred ca vrei sa zici duminica

[•NicuCJ]

) Ok.

L.E.: Am reusit dupa cateva zile de inmultit matrici pe la scoala sa ajung la un rezultat. Parca ma simt mai bine decat daca mi-ati fi trantit rezultatul in fata ) Deci, multumesc!

[•Andrei1998]

Am facut si eu problema asta si am luat pe ea 100p, explicatia este foarte bine realizata! (mai ales ca poate fi usor generalizata rezolvarea problemei pentru Fn=aFn-1+bFn-2)  
La restrictii scrie ca "0 ≤ K ≤ 1 000 000 000." Cazul k=0 nu se afla in testele problemei desi este particular si multe surse (inclusiv prima pe care am trimis-o) dau raspuns gresit sau se blocheaza pe acest caz. Eu am tratat cazul printr-un simplu if. Cred ca ar trebui incurajata o rezolvare corecta a problemei caci in timpul unui concurs o sursa ce nu trateaza cazul k=0 poate duce la pierderea de puncte valoroase.
Toate cele bune.

[•Magnvs]

f[-1]= 1 si toate cazurile tale particulare dispar
dar e o idee buna sa fie modificata restrictia in 1<=k<=10^9

[•sauron]

testele dau 100 de puncte la implementarea directa