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

Se definesc numerele lui Stirling de speta I, $s(n,m)$, ca fiind numarul de permutari de ordin $n$ cu exact $m$ cicluri. Similar, se definesc numerele lui Stirling de speta a II-a, $S(n,m)$, ca fiind numarul de partitionari ale unei multimi de $n$ elemente in $m$ submultimi nevide.

Se definesc numerele lui Stirling de speţa $I$, $s(n,m)$, ca fiind numărul de permutări de ordin $n$ cu exact $m$ cicluri. Similar, se definesc numerele lui Stirling de speţa a $II$-a, $S(n,m)$, ca fiind numărul de partiţionări ale unei mulţimi de $n$ elemente în $m$ submulţimi nevide.

h2. Cerinta

h2. Cerinţă

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

Pentru $n$ şi $m$ date, să se calculeze una dintre cele $2$ funcţii, $s(n,m)$ sau $S(n,m)$.

h2. Date de intrare

Prima linie a fisierului de intrare $stirling.in$ contine numarul de teste $T$. Urmatoarele $T$ linii contin cate un set de 3 numere, $s$, $n$ si $m$. Variabila $s$ poate lua valorile 1 si 2, avand semnificatia ca se doreste rezultatul functiei de speta I sau speta II.

Prima linie a fişierului de intrare $stirling.in$ conţine $T$, numărul de teste. Fiecare din următoarele $T$ linii conţine câte un set de $3$ numere naturale separate prin câte un spaţiu, $x$, $n$ şi $m$. Variabila $x$ poate lua valorile $1$ sau $2$. Dacă $x$ este $1$ se doreşte determinarea lui {$s(n,m)$}, iar dacă $x$ este $2$ se doreşte determinarea lui {$S(n,m)$}.

h2. Date de iesire

h2. Date de ieşire

Pentru fiecare test, afisati in fisierul $stirling.out$ rezultatul functiilor modulo 98999, fiecare pe cate un rand.

Fişierul $stirling.out$ conţine exact $T$ linii, câte una pentru fiecare test din fişierul de intrare. Linia a $i$-a conţine rezultatul, modulo $98999$, pentru testul $i$.

h2. Restrictii

h2. Indicatii de rezolvare

Ideea "naivă" de rezolvare a acestei probleme presupune generarea tuturor permutărilor de ordin $n$ şi calcularea numărului de cicluri pentru fiecare din acestea. Această rezolvare are complexitate exponenţială şi va obţine $10$ puncte.

h4. Backtracking:
 
Ideea "naiva" de rezolvare a acestei probleme presupune generarea tuturor permutarilor de ordin n si calcularea numarului de cicluri a fiecareia dintre acestea. Aceasta rezolvare are complexitatea exponentiala si va obtine 10 puncte.
 
"Stirling de speta I - Wikipedia":http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind
"Stirling de speta II - Wikipedia":http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
"Stirling de speta I - Wolfram":http://mathworld.wolfram.com/StirlingNumberoftheFirstKind.html
"Stirling de speta II - Wolfram":http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
 
In urma unei demonstratii matematice, luandu-se in considerare relatiile prezentate pe cele doua link-uri de mai devreme, rezulta recurentele :
 
<tex> s(n,m) = s(n-1,m-1) + (n-1)*s(n-1,m) </tex>
 
si
 
<tex> S(n,m) = S(n-1,m-1) + k*S(n-1,m) </tex>

În urma unor demonstraţii matematice (explicate pe larg în link-urile de mai jos), pentru funcţiile lui Stirling se pot obţine recurenţele :
<tex> s(n,m) = s(n-1,m-1) - (n-1)*s(n-1,m) </tex> şi <tex> S(n,m) = S(n-1,m-1) + m*S(n-1,m) </tex>.

h4. Recursivitate:

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":http://infoarena.ro/job_detail/429246?action=view-source.

h4. Link-uri utile
 
* "Stirling de speţa I - Wikipedia":http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind
* "Stirling de speţa II - Wikipedia":http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
* "Stirling de speţa I - Wolfram":http://mathworld.wolfram.com/StirlingNumberoftheFirstKind.html
* "Stirling de speţa II - Wolfram":http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
 

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