Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | stirling.in, stirling.out | Sursă | Arhiva Educationala |
| Autor | Arhiva Educationala | Adăugată de |  Matei-Dan Epure •motty |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Numerele lui 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.
Cerinţă
Pentru n şi m date, să se calculeze una dintre cele 2 funcţii, s(n,m) sau S(n,m).
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).
Date de ieşire
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.
Restrictii
- 1 ≤ T ≤ 1000
- 0 ≤ N, M ≤ 200
Exemplu
| stirling.in | stirling.out |
|---|---|
| 3 1 1 1 1 3 2 2 1 1 | 1 -3 1 |
Indicatii 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.
Î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 :
şi 
.
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.
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.
Link-uri utile
- Stirling de speţa I - Wikipedia
- Stirling de speţa II - Wikipedia
- Stirling de speţa I - Wolfram
- Stirling de speţa II - Wolfram
