h1. Numerele lui Stirling

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

Se numesc :

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.

Numerele lui Stirling de speta I :

h2. Cerinţă

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.
 
h2. Cerinta
 
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 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)$}.

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

* 0 < T < 1001
* 0 <= n,m <= 200

* $1 ≤ T ≤ 1000$
* $0 ≤ n, m ≤ 200$

h2. Exemplu

table(example). |_. task_id.in |_. task_id.out |

table(example). |_. stirling.in |_. stirling.out |

| 3
1 1 1
1 3 2

1
|

h2. Indicatii de rezolvare
 
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.
 
http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind
http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
http://mathworld.wolfram.com/StirlingNumberoftheFirstKind.html
http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html

h2. Indicaţii de rezolvare

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

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.

s(n,m) = s(n-1,m-1) + (n-1)*s(n-1,m)

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

S(n,m) = S(n-1,m-1) + k*S(n-1,m)

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.

Recursivitate:

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.

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. Folosind aceasta metoda veti obtine 50 de puncte, o sursa ce foloseste aceasta metoda poate fi gasita aici.

h4. Link-uri utile

Programare dinamica:

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

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")==

4864