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

Se definesc numerele lui Stirling de speţa $I$, $s(n,m)$, ca fiind coeficienţii dezvoltării <tex> x(x-1)...(x-n+1) = \displaystyle\sum_{m = 0}^n s(n,m)*x^k </tex>. 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.

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.

h2. Cerinţă

h2. Cerinta

Pentru $n$ şi $m$ date, să se calculeze una dintre cele $2$ funcţii, $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

Prima linie a fişierului de intrare $stirling.in$ conţine $T$, numărul de teste care urmează. 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)$}.

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.

h2. Date de ieşire

h2. Date de iesire

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$.

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

h2. Restrictii
* $1 ≤ T ≤ 1000$

* $0 ≤ n, m ≤ 200$

* $0 ≤ N, M ≤ 200$

h2. Exemplu

1
|

h2. Indicaţii de rezolvare

h2. Indicatii de rezolvare

Ideea naivă de rezolvare a acestei probleme este determinarea răspunsului problemei prin metoda backtracking. Această rezolvare are complexitate exponenţială şi va obţine $10$ puncte.
Î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. Backtracking:

O primă metodă de rezolvare ce foloseşte observaţia de mai sus este determinarea valorilor $s(n,m)$ sau $S(n,m)$, implementând un algoritm recursiv ce modelează relaţiile de recurenţă prezentate. Această metodă obţine $50$ de puncte. O sursă pe această idee se găseşte 'aici':job_detail/429247?action=view-source.

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.

Soluţia optimă pentru problema de faţă se bazează pe preprocesarea valorilor $s(n,m)$ şi $S(n,m)$, implemenând de asemenea relaţiile de recurenţă prezentate. Astfel, se va putea răspunde la fiecare test în timp $O(1)$, complexitatea totala fiind $O(N*M + T)$. Această rezolvare obţine $100$ de puncte. O sursă pe această idee se găseşte 'aici':job_detail/429246?action=view-source.

"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

h4. Link-uri utile

In urma unei demonstratii matematice, luandu-se in considerare relatiile prezentate pe cele doua link-uri de mai devreme, rezulta recurentele :

* "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

<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>
 
h4. Recursivitate:
 
Pentru un singur test, o metoda optima de rezolvare este cea care foloseste o functie recursiva si calculeaza la fiecare pas elementele necesare recurentei pasului actual. Totusi, daca nu este folosita memoizarea, la un numar mai mare de teste, aceasta rezolvare va iesi din timp. Aceasta metoda are complexitatea o(N*M*T). Folosind aceasta metoda veti obtine 50 de puncte, o sursa ce foloseste aceasta metoda poate fi gasita "aici":http://infoarena.ro/job_detail/429247?action=view-source.
 
h4. 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":http://infoarena.ro/job_detail/429246?action=view-source.

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

4864