* 'Dangerous Pattern / ZJU':http://acm.zju.edu.cn/show_problem.php?pid=2115

h2. 'Tritzi':problema/tritzi
h3. Algoritm de complexitate $O(N)$

Aplicarea directa a acestor relatii de recurenta conduce la un algoritm liniar, care, insa, nu se incadreaza in limita de timp.

h4. Algoritm de complexitate $O(log N)$ - varianta 1

h3. Algoritm de complexitate $O(log N)$ - varianta 1

Folosind relatiile de recurenta de mai sus, putem construi o matrice $A$ de iteratie si vom privi $T[i]$ ca pe un vector coloana. Avem relatia: $T[i] = A * T[i-1]$. $T[N] = A^N-1^ * T[1]$. $T[1]$ este cunoscut direct, iar $A^N-1^$ se poate calcula in complexitate $O(log N)$, folosind exponentiere logaritmica.

h4. Algoritm de complexitate $O(log N)$ - varianta 2

h3. Algoritm de complexitate $O(log N)$ - varianta 2

Vom calcula o matrice $T[x][i][y]$ = numarul de siruri de tritzi (mod P), de lungime $2^i^$ si pentru care primul trit are valoarea $x$, iar ultimul trit are valoarea $y$. $T[x][0][y]$ se determina direct, iar pentru $i > 0$, $T[x][i][y]$ va fi egal cu o suma din $T[x][i-1][a] * T[b][i-1][y]$, unde $a$ si $b$ sunt doua valori ({$0$}, $1$ sau {$2$}) care pot fi plasate una dupa alta.

* 'Nice Patterns Strike Back / SGU':http://acm.sgu.ru/problem.php?contest=0&problem=197
* 'Fibo / .campion 2003':http://campion.edu.ro/problems/3/106/fibo.htm

h2. Regine2

h2. 'Regine2':problema/regine2
 
Problema se rezolva prin backtracking. Pentru fiecare pozitie (in ordinea liniilor si, pentru fiecare linie, in ordinea coloanelor), se incearca amplasarea sau neamplasarea unei regine in pozitia respectiva, iar apoi se marcheaza toate pozitiile atacate de regina respectiva, pentru a nu se mai incerca amplasarea unei regine viitoare pe o pozitie deja atacata. La intoarcerea din backtracking, pozitiile marcate se demarcheaza (vom folosi, de fapt, un contor pentru fiecare pozitie, in care vom retine de cate regine deja amplasate este atacata pozitia respectiva). Singura optimizare necesara este ca, atunci cand marcam pozitiile atacate de o regina nou-amplasata, vom marca doar pozitiile pe care vom incerca sa amplasam o regina in viitor (adica doar inspre directiile: est, sud-est, sud, sud-vest, si nu in toate cele $8$ directii).
 
h3. Probleme asemanatoare
 
* 'Problema celor $N$ regine [ clasica ] & co.':http://acm.fzu.edu.cn/reference/Search%20Techniques.htm

h2. Rfinv