Problema Șir – OJI 2017, Clasa a 10-a

Problema Șir – OJI 2017, Clasa a 10-a

Rezumat

Considerăm șirurile de lungime nn care încep cu 11 cu proprietatea că fiecare element este mai mare decât predecesorul lui cu cel mult 11 Să se determine numărul de șiruri ce se termină în uu și respectiv numărul de șiruri în care un element apare de cel mult rr ori.

Soluție

Răspunsul pentru prima cerință este Cn1u1C_{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 uu secvențe, iar noi trebuie să alegem capetele acestora. Cum ultima secvență are capătul fixat în poziția nn rămâne să alegem capetele doar pentru primele u1u - 1 secvențe. Acestea trebuie să ia valori distincte din mulțimea {1,2,,n1}\{1, 2, \ldots, n - 1\} așa că numărul lor este Cn1u1C_{n - 1}^{u - 1} Având nevoie de o singură combinare, o vom calcula folosind invers modular, pe baza formulei:

Cn1u1=(n1)!(u1)!1(nu)!1C_{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 dp[i]\mathrm{dp}[i] numărul de șiruri de lungime ii cu proprietatea dată. Putem obține un șir de lungime ii adăugând jj valori egale la un șir de lungime iji - j unde 1jr1 \le j \le r Valorile adăugate sunt unic determinate de ultimul element al șirului de lungime iji - j Adică, dacă acesta se termină în xx atunci șirul nou se va termina în jj de x+1x + 1 Deci, recurența este:

dp[i]=dp[i1]+dp[i2]++dp[ir]\mathrm{dp}[i] = \mathrm{dp}[i - 1] + \mathrm{dp}[i - 2] + \cdots + \mathrm{dp}[i - r]

Dinamica poate fi calculată imediat în O(nr)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 dp[i]\mathrm{dp}[i] și dp[i1]\mathrm{dp}[i - 1]

dp[i]=dp[i1]+dp[i2]++dp[ir]dp[i1]=dp[i2]+dp[i3]++dp[ir1]\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:

dp[i]dp[i1]=dp[i1]dp[ir1]\mathrm{dp}[i] - \mathrm{dp}[i - 1] = \mathrm{dp}[i - 1] - \mathrm{dp}[i - r - 1]

De unde:

dp[i]=2dp[i1]dp[ir1]\mathrm{dp}[i] = 2 \cdot \mathrm{dp}[i - 1] - \mathrm{dp}[i - r - 1]

Evident, complexitatea pentru calcularea noii recurențe este O(n)O(n)

Sursă C++

Problema Șir
#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';
}
return 0;
}

Dacă ai vreo nedumerire cu privire la problema Șir, 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