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

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.

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ţă

h2. Date de intrare

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

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

h2. Restrictii
* $1 ≤ T ≤ 1000$

* $0 ≤ N, M ≤ 200$

* $0 ≤ n, m ≤ 200$

h2. Exemplu

1
|

h2. Indicatii de rezolvare

h2. Indicaţii 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.

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 :

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

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.

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.

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.

h4. Link-uri utile

4864