Enunțul problemei sir, de clasa a 10-a, dată în 2017 la OJI, se găsește pe InfoArena și PbInfo.
Rezumat
Considerăm șirurile de lungime $n$, care încep cu $1$, cu proprietatea că fiecare element este mai mare decât predecesorul lui cu cel mult $1$. Să se determine numărul de șiruri ce se termină în $u$, și respectiv numărul de șiruri în care un element apare de cel mult $r$ ori.
Soluție
Răspunsul pentru prima cerință este $C_{n - 1}^{u - 1}$, iar explicația este exact cea de la numărul de partiții ordonate ale unui număr natural, din acest articol. Șirul nostru este partiționat în $u$ secvențe, iar noi trebuie să alegem capetele acestora. Cum ultima secvență are capătul fixat în poziția $n$, rămâne să alegem capetele doar pentru primele $u - 1$ secvențe. Acestea trebuie să ia valori distincte din mulțimea $\{1, 2, \ldots, n - 1\}$, așa că numărul lor este $C_{n - 1}^{u - 1}$. Având nevoie de o singură combinare, o vom calcula folosind invers modular, pe baza formulei:
$$C_{n - 1}^{u - 1} = (n - 1)! \cdot (u - 1)!^{-1} \cdot (n - u)!^{-1}$$
La a doua cerință vom folosi programare dinamică astfel: Notăm cu $\mathrm{dp}[i]$ numărul de șiruri de lungime $i$ cu proprietatea dată. Putem obține un șir de lungime $i$ adăugând $j$ valori egale la un șir de lungime $i - j$, unde $1 \le j \le r$. Valorile adăugate sunt unic determinate de ultimul element al șirului de lungime $i - j$. Adică, dacă acesta se termină în $x$, atunci șirul nou se va termina în $j$ de $x + 1$. Deci, recurența este:
$$\mathrm{dp}[i] = \mathrm{dp}[i - 1] + \mathrm{dp}[i - 2] + \cdots + \mathrm{dp}[i - r]$$
Dinamica poate fi calculată imediat în $O(n \cdot r)$, însă poate fi optimizată foarte ușor făcând următoarea observație. Scriem una sub alta recurențele pentru $\mathrm{dp}[i]$ și $\mathrm{dp}[i - 1]$:
$$\begin{align}
\mathrm{dp}[i] & = \mathrm{dp}[i - 1] + \mathrm{dp}[i - 2] + \cdots + \mathrm{dp}[i - r]\\
\mathrm{dp}[i - 1] & = \mathrm{dp}[i - 2] + \mathrm{dp}[i - 3] + \cdots + \mathrm{dp}[i - r - 1]
\end{align}$$
Dacă scădem cele două relații, se vor reduce o grămadă de termeni și vom obține:
$$\mathrm{dp}[i] - \mathrm{dp}[i - 1] = \mathrm{dp}[i - 1] - \mathrm{dp}[i - r - 1]$$
De unde:
$$\mathrm{dp}[i] = 2 \cdot \mathrm{dp}[i - 1] - \mathrm{dp}[i - r - 1]$$
Evident, complexitatea pentru calcularea noii recurențe este $O(n)$.
Sursă C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <bits/stdc++.h> using namespace std; const int NMAX = 100010; const int MOD = 20173333; ifstream fin("sir9.in"); ofstream fout("sir9.out"); int p, n, u; int dp[NMAX]; int pwr(int a, int b) { if (!b) return 1; if (b & 1) return 1LL * a * pwr(1LL * a * a % MOD, b >> 1) % MOD; return pwr(1LL * a * a % MOD, b >> 1); } int modInv(int n) { return pwr(n, MOD - 2); } int fact(int n) { int f = 1; for (int i = 2; i <= n; i++) f = 1LL * f * i % MOD; return f; } int main() { fin >> p >> n >> u; if (p == 1) fout << 1LL * fact(n - 1) * modInv(fact(u - 1)) % MOD * modInv(fact(n - u)) % MOD << '\n'; else { dp[0] = dp[1] = 1; for (int i = 2; i <= n; i++) dp[i] = (2 * dp[i - 1] - (i >= u - 1 ? dp[i - u - 1] : 0) + MOD) % MOD; fout << dp[n] << '\n'; } fout.close(); return 0; } |
Dacă ai vreo nedumerire cu privire la problema sir, lasă un comentariu și te voi ajuta 🙂
Îți place conținutul acestui site?
Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!