==Include(page="template/taskheader" task_id="stirling")==
 

h1. Numerele lui Stirling
Se numesc :
Numerele lui Stirling de speta I :

s(n,m) = numarul de permutari de ordin &n& cu exact &m& cicluri.

s(n,m) = numarul de permutari de ordin ~n~ cu exact ~m~ cicluri.

Numerele lui Stirling de speta II :

S(n,m) = numarul de partitionari ale unei submultimi de &n& elemente in &m& submultimi nevide.

S(n,m) = numarul de partitionari ale unei submultimi de ~n~ elemente in ~m~ submultimi nevide.

h2. Cerinta

Pentru ~n~ si ~m~ date, sa se calculeze una dintre cele 2 functii, &s(n,m)& sau ~S(n,m)~.

Pentru ~n~ si ~m~ date, sa se calculeze una dintre cele 2 functii, ~s(n,m)~ sau ~S(n,m)~.

h2. Date de intrare

Programare dinamica:
Solutia optima a acestei probleme este cea care foloseste metoda programarii dinamice. astfel vor fi precalculate 2 matrici s[N][M] si S[N][M] cu semnificatia s[i][j]=s(i,j) si S[i][j]=S(i,j). Folosindu-se aceasta metoda, la fiecare test vom raspunde in o(1) la intrebare si deci complexitatea va fi o(N*M + T). Aceasta rezolvare obtine 100 de puncte si o sursa ce o foloseste poate fi gasita aici.

 
==Include(page="template/taskfooter" task_id="stirling")==