h1. Numerele lui Stirling
== include(page="template/taskheader" task_id="stirling") ==
Se numesc :
Numerele lui Stirling de speta I :
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)~.
Poveste şi cerinţă...
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.
Fişierul de intrare $stirling.in$ ...
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.
În fişierul de ieşire $stirling.out$ ...
h2. Restrictii
h2. Restricţii
* 0 < T < 1001
* 0 <= n,m <= 200
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. task_id.in |_. task_id.out |
| 3
1 1 1
1 3 2
2 1 1
| 1
-3
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
In urma unei demonstratii matematice, luandu-se in considerare relatiile prezentate pe cele doua link-uri de mai devreme, rezulta recurentele :
s(n,m) = s(n-1,m-1) + (n-1)*s(n-1,m)
S(n,m) = S(n-1,m-1) + k*S(n-1,m)
Recursivitate:
table(example). |_. stirling.in |_. stirling.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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.
h3. Explicaţie
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") ==
