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$ din primele $i$ cifre ale 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 numara subsirurile distincte ( adica sa nu numaram subsiruri egale de doua ori ), daca suntem in starea {$(j, i, r)$} actualizam starea {$(j+1, first[cif][i+1], (r*10+cif) mod K)$} daca si numai daca intre pozitiile $i+1$ si $first[cif][i+1]-1$ in numarul $N$ nu mai apare nici o cifra {$cif$}. Acest lucru poate fi deasemenea calculat prin preprocesare, inainte de a incepe algoritmul de programare dinamica.
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.
Complexitatea finala a algoritmului este {$O(K * L^2^)$}, unde L este numarul de cifre ale numarului {$N$}.
h2. Radiatie
