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

• Dificultate:
• Autor: Ciprian Cheșcă
• Online: InfoArena, PbInfo

Rezumat

În problema 100m, ni se cere să determinăm numărul modalităților în care cei $n$ 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 = 3$ numerotând concurenții cu $1$ $2$ $3$ 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, \ldots, n\}$ în $1, 2, \ldots, n$ submulțimi. Pentru fiecare partiție, submulțimea $i$ reprezintă grupul de concurenți care s-au clasat pe poziția $i$ (fiind la egalitate). De exemplu, partiția $\{1\}, \{2, 5\}, \{4\}, \{3, 6, 7\}$ are semnificația:

Concurentul $1$ s-a clasat pe prima poziție, concurenții $2$ și $5$ pe a doua poziție, fiind la egalitate, concurentul $4$ pe a treia poziție, iar concurenții $3$ $6$ și $7$ au terminat proba simultan, situându-se pe ultima poziție.

Pe fiecare astfel de partiție de $k$ submulțimi o putem permuta în toate modurile posibile $\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 $k$ De asemenea, vom avea în vedere utilizarea aritmeticii modulare, deoarece rezultatul trebuie afișat modulo $666013$

Sursă C++

#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