X[n] \\
X[n - 1] \end{array} \right)\]  </tex>

Iar cum o matrice o putem ridica la o putere în număr logaritmic de paşi, putem afla <tex> $X[n]$ </tex> mult mai repede.

Iar cum o matrice o putem ridica la o putere în număr logaritmic de paşi, putem afla <tex> $X[n]$ </tex> mult mai repede.
 
h3. *Problema 7* (ACM ICPC 1997)
 
Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $N x M (N <= 20, M <= 20)$ cu dominouri.
 
h3. Soluţie:
 
Poate părea surprinzător, dar pentru această problemă, deşi pare foarte grea, există o formulă:
 
<tex> ${2}^{\frac{M*N}{2}} * {(\cos^{2}\frac{m*pi}{M+1} + cos^{2}\frac{n*pi}{N+1})}^{\frac{1}{4}}$ </tex>
 
pentru $0 < m < M+1, 0 < n < N+1$. Şi mai surprinzător este că această expresie ce conţine numere iraţionale are ca rezultat un număr întreg. Pentru o demonstraţie a acestei formule puteţi să intraţi pe adresa [4]. Ar fi anormal ca să ştim o asemenea formulă pe de rost în speranţa că vom primi problema la vreun concurs. Dimensiunile mici ale problemei o făceau abordabilă printr-un algoritm ce combină $programarea dinamică$ cu $backtrackingul$ pe care îl vom prezenta în numărul următor.