h3. (problema medie, clasele 11-12)
Problema se rezolva prin metoda programarii dinamice. Fie {$M[j][i]{@[r]@}$} numarul de moduri de a alege subsiruri distincte de lungime $j$ care contin ca ultima cifra cea de-a $i$-a cifra a numarului {$N$}, subsiruri care sa dea restul $r$ la impartirea {$K$}. Daca ne aflam in starea {$(j, i, r)$} putem sa actualizam starea {$(j+1, first[cif][i+1], (r*10+cif) mod K)$}, considerand ca am adaugat la sfarsitul fiecarui subsir definit de {$(j, i, r)$} cifra {$cif$}. Prin {$first[cif][i]$} se defineste prima aparitie in numarul $N$ a cifrei $cif$ dupa pozitia {$i$}. Tabloul $first$ va fi, evident, preprocesat. Pentru a nu numara subsirurile egale de doua ori, trebuie sa initializam pentru lungimea 1 doar pozitiile care contin pentru prima oara o cifra. Astfel initializam starile {$(1, @first[cif][0]@, cif mod K)$} cu 1. Pe parcurs, adunam la solutie starile care au lungimea cuprinsa intre $A$ si $B$ si care au $r$ egal cu 0.
Problema se rezolva prin metoda programarii dinamice. Fie {$M[j][i]{@[r]@}$} numarul de moduri de a alege subsiruri distincte de lungime $j$ care contin ca ultima cifra cea de-a $i$-a cifra a numarului {$N$}, subsiruri care sa dea restul $r$ la impartirea {$K$}. Daca ne aflam in starea {$(j, i, r)$} putem sa actualizam starea {$(j+1, first[cif][i+1], (r*10+cif) mod K)$}, considerand ca am adaugat la sfarsitul fiecarui subsir definit de {$(j, i, r)$} cifra {$cif$}. Prin {$first[cif][i]$} se defineste prima aparitie in numarul $N$ a cifrei $cif$ dupa pozitia {$i$}. Tabloul $first$ va fi, evident, preprocesat. Pentru a nu numara subsirurile egale de doua ori, trebuie sa initializam pentru lungimea 1 doar pozitiile care contin pentru prima oara o cifra. Astfel initializam starile {$(1, @first[cif][0]@, cif mod K)$} cu 1, pentru cif = 1..9 (ca nu cumva un subsir sa inceapa cu 0). Pe parcurs, adunam la solutie starile care au lungimea cuprinsa intre $A$ si $B$ si care au $r$ egal cu 0.
Complexitatea finala a algoritmului este {$O(K * L^2^)$}, unde L este numarul de cifre ale numarului {$N$}.
