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$ 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.
Complexitatea finala a algoritmului este {$O(K * L^2^)$}, unde L este numarul de cifre ale numarului {$N$}.
h2. Radiatie
