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':infoarena.ro/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>.

Ş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