Problema Șir – OJI 2017, Clasa a 10-a
Rezumat
Considerăm șirurile de lungime care încep cu cu proprietatea că fiecare element este mai mare decât predecesorul lui cu cel mult Să se determine numărul de șiruri ce se termină în și respectiv numărul de șiruri în care un element apare de cel mult ori.
Soluție
Răspunsul pentru prima cerință este 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 secvențe, iar noi trebuie să alegem capetele acestora. Cum ultima secvență are capătul fixat în poziția rămâne să alegem capetele doar pentru primele secvențe. Acestea trebuie să ia valori distincte din mulțimea așa că numărul lor este Având nevoie de o singură combinare, o vom calcula folosind invers modular, pe baza formulei:
La a doua cerință vom folosi programare dinamică astfel: Notăm cu numărul de șiruri de lungime cu proprietatea dată. Putem obține un șir de lungime adăugând valori egale la un șir de lungime unde Valorile adăugate sunt unic determinate de ultimul element al șirului de lungime Adică, dacă acesta se termină în atunci șirul nou se va termina în de Deci, recurența este:
Dinamica poate fi calculată imediat în însă poate fi optimizată foarte ușor făcând următoarea observație. Scriem una sub alta recurențele pentru și
Dacă scădem cele două relații, se vor reduce o grămadă de termeni și vom obține:
De unde:
Evident, complexitatea pentru calcularea noii recurențe este
Sursă C++
#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