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

Stim ca $M{~i~}$ este egal cu $Z$ * $M{~i-1~}$ si mai stim ca $M{~i-1~}$ este egal cu $Z * M{~i-2~}$. Din proprietatea de asociativitate a inmultirii matricilor rezulta ca $M{~i~}$ este egal cu $Z^2^ * M{~i-2~}$. Inductiv rezulta ca $M{~i~}$ = $Z^N-1^$ * $M{~1~}$. 'Soluţia':/job_detail/372680?action=view-source optima se foloseşte de 'ridicarea la putere în timp logaritmic':/problema/lgput, avand complexitatea finala de $O(log K * CONST)$, unde $CONST$ este numarul de operatii necesar pentru a inmulti intre ele puterile matricii constante. Avand in vedere ca toate acestea sunt patratice de latura $2$, $CONST$ va fi egal cu $2^3^$, adica $8$.

Stim ca $M{~i~}$ este egal cu $Z$ * $M{~i-1~}$ si mai stim ca $M{~i-1~}$ este egal cu $Z * M{~i-2~}$. Din proprietatea de asociativitate a inmultirii matricilor rezulta ca $M{~i~}$ este egal cu $Z^2^ * M{~i-2~}$. Inductiv rezulta ca $M{~i~}$ = $Z^N-1^$ * $M{~1~}$. 'Soluţia':/job_detail/372680?action=view-source optima se foloseşte de 'ridicarea la putere în timp logaritmic':/problema/lgput, avand complexitatea finala de $O(log K * CONST)$. $CONST$ este numarul de operatii efectuate la fiecare pas al ridicarii la putere si este egal cu latura matricii constante la puterea a $3$-a, adica $8$.

h2. Aplicaţii