Zadanie

Ako sa tak blíži čas jesenného sústredenia, treba začať hľadať chatu. Keďže však KSP všetky financie od sponzorov drží v kryptomenách, nič luxusné si nemôže dovoliť. “Zvýšme účastnícky poplatok na 150 eur!”, navrhol Dávid. “Tak to vôbec! Kde si také niečo videl? To radšej ušetríme na záchodoch…”, rozhorčuje sa Emma vymýšľajúc ako z nedostatku toaliet spraviť zábavu. “Hmmm, len aby to nebolo nespravodlivé…”.

Úloha

Chata má iba jeden záchod. Každú hodinu vedúci jednotne náhodne vyžrebujú jedného účastníka alebo účastníčku, ktorej umožnia návštevu toalety. Vediac dĺžku trvania sústredenia a počet účastníkov, Emma by rada vedela odpoveď na nasledovnú otázku. Koľko možných žrebovaní má za následok, že práve jedna osoba navštívi toaletu najviackrát zo všetkých?

Formát vstupu

Na prvom riadku sa nachádza číslo \(t\) – počet sústredení. Na \(i\)-tom z nasledovných \(t\) riadkov sa nachádzajú čísla \(n_i, k_i\) – počet účastníkov a počet hodín \(i\)-teho sústredenia.

Formát výstupu

Vypíšte \(t\) riadkov. Na \(i\)-tom z nich odpoveď na \(i\)-tu otázku modulo \(10^9 + 7\).

Hodnotenie

Úloha má 8 sád vstupov. Platia v nich nasledovné obmedzenia:

1 2 3 4,5 6 7,8
\(1 \leq t \leq\) 10 10 10 10 3 10
\(1 \leq n \leq\) 10 100 4 50 100 100
\(1 \leq k \leq\) 10 4 100 50 100 100

Príklady

Input:

4
2 2
6 10
5 9
4 4

Output:

2
2472
600
28

V prvom prípade môže ísť na záchod dvakrát prvý účastník, alebo dvakrát druhá účastníčka. Vo všetkých ostatných možnostiach by nešla na toaletu najviac krát práve jedna osoba.

Ked súťažná programátorka počuje “počet možností”, okamžite by jej malo napadnúť slovo “dynamika”.

Hrubá sila

Pár bodov sa dalo získať za riešenie hrubou silou. Mohli sme napríklad vyskúšať všetky možné žrebovania a zrátať vyhovujúce.

Obmedzenia v sadách

Niektoré sady mali malé obmedzenia na \(n\), alebo \(k\). Tieto sady sa pravdepodobne dali riešiť odvodením vhodných matematických vzorcov.

Takmer vzorové riešenie

Nuž, ako by sme sa na túto úlohu mohli pozerať? Ako funkčný sa ukáže prístup, kde postupne skúsime všetky možnosti pre počet návštev záchoda najviackrát vyžrebovaného účastníka.

Keď vieme, koľkokrát bol vyžrebovaný najšťastnejší účastník, nech je to \(w\), potrebujeme zodpovedať na nasledovnú otázku. Koľkými spôsobmi možno rozdeliť \(k-w\) návštev toalety medzi zvyšných \(n-1\) účastníčiek tak, že každá získa nanajvýš \(w-1\) návštev?. Pre účastníčku, ktorá bola vyžrebovaná \(w\) krát je \(n\) možností, preto odpoveď na našu otázku potrebujeme prenásobiť \(n\). Odpoveď na celú úlohu potom bude súčet cez všetky možné maximálne počty vyžrebovaní najúspešnejšieho účastníka.

Budeme teda potrebovať zrátať dynamiku dp[x][y][z], ktorá bude hovoriť, koľkými možnosťami možno rozdeliť x vyžrebovaní medzi y účastničiek tak, že každá bude vyžrebovaná nanajvýš z krát. Triviálne prípady, kde aspoň jedno z x, y, z je 0, vieme určiť jednoducho. Ako následne zrátame dp[x][y][z]? Skúsime všetky možnosti pre to, koľkokrát bol vyžrebovaný posledný účastník. Bude teda platiť: \[dp[x][y][z] = \sum_{i=0}^z dp[x-i][y-1][z]\]

Priamočiary pohľad na toto riešenie hovorí, že jeho časová zložitosť bude \(O(nk^3)\). Pamäťová zložitosť je \(O(nk^2)\). Keďže nám vždy stačia posledné dva riadky tabuľky dp, vieme túto zložitosť zlepšiť na \(O(nk)\).

#include <bits/stdc++.h>

using namespace std;

const int mod = 1000000007;

int main() {
    int TC, n, k;
    cin >> TC;
    while(TC--) {
        cin >> n >> k;

        if(n == 1) {
            cout << 1 << '\n';
            continue;
        }

        // Inicializujeme dp: kolkymi sposobmi vieme rozdelit `total`
        // bodov medzi `people` ludi zatialco kazdy z nich dostane nanajvys `mx_points` bodov
        long long dp[k + 1][n + 1][k + 1]; // total, people, mx_points
        for(int total = 0; total <= k; total++)
            for(int people = 0; people <= n; people++)
                for(int mx_points = 0; mx_points <= k; mx_points++)
                    dp[total][people][mx_points] = !total;

        // Vypocitame netrivialne pripady dp
        for(int total = 1; total <= k; total++) {
            for(int people = 1; people <= n; people++) {
                for(int mx_points = 1; mx_points <= k; mx_points++) {
                    dp[total][people][mx_points] = 0;
                    // Skusime vsetky moznosti pre pocet bodov ziskanych poslednou ucastnickou
                    for(int last = 0; last <= mx_points && total - last >= 0; last++) {
                        dp[total][people][mx_points] += dp[total - last][people - 1][mx_points];
                        if(dp[total][people][mx_points] >= mod)
                            dp[total][people][mx_points] -= mod;
                    }
                }
            }
        }

        // Skusime vsetky moznosti pre pocet bodov ziskanych vitazom
        long long ans = 0;
        for(int winner_points = 1; winner_points <= k; winner_points++) {
            ans += dp[k - winner_points][n - 1][winner_points - 1];
            if(ans >= mod)
                ans -= mod;
        }

        cout << (ans * n) % mod << '\n';
    }

    return 0;
}

mod = 1000000007

TC = int(input())
for _ in range(TC):
    n, k = map(int, input().split())
    
    if n == 1:
        print(1)
        continue
    
    dp = []
    for total in range(k + 1):
        dp.append([])
        for people in range(n + 1):
            dp[-1].append([])
            for mx_points in range(k + 1):
                dp[-1][-1].append(1 if total == 0 else 0)

    for total in range(1, k + 1):
        for people in range(1, n + 1):
            for mx_points in range(1, k + 1):
                dp[total][people][mx_points] = 0
                for last in range(mx_points + 1):
                    if total - last < 0:
                        break
                    dp[total][people][mx_points] += dp[total - last][people - 1][mx_points]
                    if dp[total][people][mx_points] >= mod:
                        dp[total][people][mx_points] -= mod

    ans = 0
    for winner_points in range(1, k + 1):
        ans += dp[k - winner_points][n - 1][winner_points - 1]
        if ans >= mod:
            ans -= mod

    print((ans * n) % mod)

Vzorové riešenie

Ako pri dynamikách býva, aj predchádzajúce riešenie sa dá zoptimalizovať. Takáto optimalizácia často spočíva v tom, že sa zbavíme jedného rozmeru a možno pri tom nejak pomiešame zvyšné rozmery tak, aby sme tretí rozmer nepotrebovali.

Môžeme iterovať cez maximálny povolený počet vyžrebovaní jedného účastníka. Počas toho budeme počítať dynamiku iba so zvyšnými dvoma rozmermi.

Časová zložitosť riešenia po takejto optimalizácii bude \(O(nk^2)\). Pamäťová zložitosť je \(O(nk)\).

#include <bits/stdc++.h>

using namespace std;

const int mod = 1000000007;

int main() {
    int TC, n, k;
    cin >> TC;
    while(TC--) {
        cin >> n >> k;

        if(n == 1) {
            cout << 1 << '\n';
            continue;
        }   

        long long dp[n][k]; // people, total
        long long ans = 0;
        for(int mx_points = 0; mx_points < k; mx_points++) {
            long long k_limit = k - mx_points - 1;
            for(int people = 0; people < n; people++)
                for(int total = 0; total <= k_limit; total++)
                    dp[people][total] = !total;

            for(int people = 1; people < n; people++) {
                for(int total = 1; total <= k_limit; total++) {
                    long long &current = dp[people][total];
                    current +=
                        dp[people][total - 1] +
                        dp[people - 1][total] -
                        (total > mx_points ? dp[people - 1][total - mx_points - 1] - mod : 0); 
                    current -= mod * (current >= mod);
                    current -= mod * (current >= mod);
                }   
            }   

            ans += dp[n - 1][k_limit];
            ans -= mod * (ans >= mod);
        }   

        cout << (ans * n) % mod << '\n';
    }   
}

mod = 1000000007

TC = int(input())
for _ in range(TC):
    n, k = list(map(int, input().split()))
    
    if n == 1:
        print(1)
        continue

    dp = [[-1 for j in range(k)] for i in range(n)]
    ans = 0
    for mx_points in range(k):
        k_limit = k - mx_points - 1
        for people in range(n):
            for total in range(k_limit + 1):
                dp[people][total] = 1 if total == 0 else 0
        for people in range(1, n):
            for total in range(1, k_limit + 1):
                dp[people][total] += dp[people][total - 1] + dp[people - 1][total] - (dp[people - 1][total - mx_points - 1] if total > mx_points else 0)
                for i in range(2):
                    dp[people][total] -= mod * (1 if dp[people][total] >= mod else 0)
        ans += dp[n - 1][k_limit]
        ans -= mod * (1 if ans >= mod else 0)
    print((ans * n) % mod)

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.