== include(page="template/taskheader" task_id="stirling") ==
==Include(page="template/taskheader" task_id="stirling")==
Poveste şi cerinţă...
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.
h2. Cerinţă
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
Fişierul de intrare $stirling.in$ ...
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 ieşire
În fişierul de ieşire $stirling.out$ ...
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. Restricţii
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 1000$
* $0 ≤ n, m ≤ 200$
h2. Exemplu
table(example). |_. stirling.in |_. stirling.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 3
1 1 1
1 3 2
2 1 1
| 1
-3
1
|
h2. Indicaţii 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>.
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.
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.
h3. Explicaţie
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") ==
==Include(page="template/taskfooter" task_id="stirling")==
