Problema 100m – ONI 2017, Clasa a 10-a

Problema 100m – ONI 2017, Clasa a 10-a

Rezumat

În problema 100m, ni se cere să determinăm numărul modalităților în care cei nn concurenți ai unei probe de 100 metri pot trece linia de finish, știind că între aceștia pot exista și egalități. De exemplu, pentru n=3n = 3 numerotând concurenții cu 11 22 33 vom obține următoarele clasamente:

(1) (2) (3)
(1) (3) (2)
(2) (1) (3)
(2) (3) (1)
(3) (1) (2)
(3) (2) (1)
(1 = 2) (3)
(3) (1 = 2)
(1 = 3) (2)
(2) (1 = 3)
(2 = 3) (1)
(1) (2 = 3)
(1 = 2 = 3)

Soluție

Această problemă este o aplicație obișnuită la Numerele lui Stirling de speța a II-a. Vom considera, pe rând, toate partițiile mulțimii {1,2,,n}\{1, 2, \ldots, n\} în 1,2,,n1, 2, \ldots, n submulțimi. Pentru fiecare partiție, submulțimea ii reprezintă grupul de concurenți care s-au clasat pe poziția ii (fiind la egalitate). De exemplu, partiția {1},{2,5},{4},{3,6,7}\{1\}, \{2, 5\}, \{4\}, \{3, 6, 7\} are semnificația:

Concurentul 11 s-a clasat pe prima poziție, concurenții 22 și 55 pe a doua poziție, fiind la egalitate, concurentul 44 pe a treia poziție, iar concurenții 33 66 și 77 au terminat proba simultan, situându-se pe ultima poziție.

Pe fiecare astfel de partiție de kk submulțimi o putem permuta în toate modurile posibile (k!\htmlClass{katexified}{(} k! pentru că acele grupuri de sportivi pot sosi în orice ordine. Pentru punctajul maxim vom precalcula eficient numere lui Stirling, cât și factorialul corespunzător fiecărui kk De asemenea, vom avea în vedere utilizarea aritmeticii modulare, deoarece rezultatul trebuie afișat modulo 666013666013

Sursă C++

Problema 100m
#include <fstream>
#define NMAX 5010
#define MOD 666013
std::ifstream fin("100m.in");
std::ofstream fout("100m.out");
int n;
long long int sol;
long long int fact[NMAX];
long long int stir[2][NMAX];
int main() {
fin >> n;
bool ind = 0;
stir[ind][0] = 1;
for (int i = 1; i <= n; i++, ind ^= 1, stir[0][0] = stir[1][0] = 0)
for (int j = 1; j <= i; j++)
stir[!ind][j] = (stir[ind][j - 1] + stir[ind][j] * j) % MOD;
fact[1] = 1;
for (int i = 2; i <= n; i++)
fact[i] = fact[i - 1] * i % MOD;
for (int i = 1; i <= n; i++)
sol = (sol + stir[ind][i] * fact[i]) % MOD;
fout << sol << '\n';
return 0;
}

Dacă ai vreo nedumerire cu privire la problema 100m, lasă un comentariu și te voi ajuta

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii