Rezolvare completă PbInfo #2000 Sir9

Corneluș a învățat să numere. El pornește întotdeauna de la 1, numără din 1 în 1, nu greșește niciodată numărul următor, însă ezită uneori și atunci spune numărul curent de mai multe ori. Sora lui, Corina, îl urmărește și face tot felul de calcule asupra modurilor în care numără fratele ei. Astfel, ea urmărește până la cât numără (U), câte numere spune în total (N) și, pentru a aprecia cât de ezitant este, numărul maxim de repetări (R) ale unei valori. De exemplu, el poate număra până la 8 astfel: 1 2 3 3 4 5 6 7 7 7 7 8 8. În acest caz, numără până la 8 (U=8), spune 13 numere (N=13) și ezită cel mai mult la 7, spunându‑l de 4 ori (R=4).

Cerințe

1) Cunoscând numărul total de numere N și ultimul număr spus U, trebuie să calculați câte șiruri diferite au exact N numere și se termină cu numărul U.
2) Cunoscând numărul total de numere N și numărul maxim de repetări R ale unei valori, trebuie să calculați câte șiruri diferite au exact N numere și fiecare valoare se repetă de cel mult R ori.
Deoarece numărul de șiruri poate fi foarte mare, calculați restul împărțirii acestui număr la 20173333.

Date de intrare

Din fișierul sir9.in se citesc trei numere naturale, P, N și X, scrise în această ordine, cu câte un spațiu între ele. P poate avea una dintre valorile 1 sau 2, iar N este numărul de numere din șir. Când P are valoarea 1, numărul X reprezintă ultimul număr spus (U), iar când P are valoarea 2, X reprezintă numărul maxim de repetări ale unei valori (R).

Date de ieșire

În fișierul sir9.out se scrie o singură valoare, astfel:

  • dacă P a avut valoarea 1, valoarea reprezintă numărul de șiruri distincte care au exact N numere și se termină cu numărul X;
  • dacă P a avut valoarea 2, valoarea reprezintă numărul de șiruri distincte care au exact N numere și fiecare număr se repetă de cel mult X ori.

În ambele cazuri, deoarece numărul rezultat poate fi foarte mare, se va scrie restul împărțirii acestui număr la 20173333.

Restricții și precizări

  • 1 ≤ N ≤ 100000
  • X ≤ N
  • testele cu P=1 vor totaliza 50% din punctaj, restul de 50% din punctaj fiind pentru P=2;
  • pentru teste cumulând 50 de puncte valoarea lui N nu depășește 1000;
  • Ultima valoare spusă poate să apară de mai multe ori.

Exemplul 1

sir9.in

1 5 3

sir9.out

6

Explicație

Se rezolvă cerința 1. Pentru N=5, X=3, sunt 6 șiruri care au exact N numere și se termină cu 3: 1 1 1 2 3, 1 1 2 2 3, 1 1 2 3 3, 1 2 2 2 3, 1 2 2 3 3, 1 2 3 3 3.

Exemplul 2

sir9.in

2 5 2

sir9.out

8

Explicație

Se rezolvă cerința 2. Pentru N=5, X=2, sunt 8 șiruri care au exact N numere și fiecare număr se repetă de cel mult 2 ori: 1 1 2 2 3, 1 1 2 3 3, 1 1 2 3 4, 1 2 2 3 3, 1 2 2 3 4, 1 2 3 3 4, 1 2 3 4 4, 1 2 3 4 5.

Exemplul 3

sir9.in

2 10 3

sir9.out

274

Explicație

Se rezolvă cerința 2. Pentru N=10, X=3, sunt 274 de șiruri care au exact 10 numere și fiecare număr se repetă de cel mult 3 ori.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Sir9:

#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>

using namespace std;

static const int kModulo = 20173333;

int main() {
    ifstream cin("sir9.in");
    ofstream cout("sir9.out");

    int T, N, X; assert(cin >> T >> N >> X);
    assert(1 <= T && T <= 2);
    assert(1 <= N && N <= 100 * 1000);
    assert(1 <= X && X <= N);
    if (T == 1) {
        vector<int> prime(N + 1, 0);
        for (int i = 2; i <= N; ++i)
            if (prime[i] == 0)
                for (int j = i; j <= N; j += i)
                    prime[j] = i;

        vector<int> exponent(N + 1, 0);
        for (int i = N - X + 1; i <= N - 1; ++i)
            for (int j = i; j > 1; j /= prime[j])
                ++exponent[prime[j]];
        for (int i = 1; i < X; ++i)
            for (int j = i; j > 1; j /= prime[j])
                --exponent[prime[j]];

        int answer = 1;
        for (int i = 1; i <= N; ++i)
            for (int j = 0; j < exponent[i]; ++j)
                answer = (1LL * answer * i) % kModulo;
        cout << answer << "
";
        return 0;
    }

    vector<int> fibK(N + 2, 0);
    fibK[1] = 1;
    fibK[2] = 1;
    for (int i = 3; i <= N + 1; ++i) {
        fibK[i] = (2 * fibK[i - 1] - fibK[max(i - X - 1, 0)]) % kModulo;
        if (fibK[i] < 0)
            fibK[i] += kModulo;
    }
    cout << fibK[N + 1] << "
";
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2000 Sir9

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2000 Sir9 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!