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) {
1 << '\n';
cout << 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++) {
0;
dp[total][people][mx_points] = // Skusime vsetky moznosti pre pocet bodov ziskanych poslednou ucastnickou
for(int last = 0; last <= mx_points && total - last >= 0; last++) {
1][mx_points];
dp[total][people][mx_points] += dp[total - last][people - 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++) {
1][winner_points - 1];
ans += dp[k - winner_points][n - if(ans >= mod)
ans -= mod;
}
'\n';
cout << (ans * n) % mod <<
}
return 0;
}
= 1000000007
mod
= int(input())
TC for _ in range(TC):
= map(int, input().split())
n, k
if n == 1:
print(1)
continue
= []
dp for total in range(k + 1):
dp.append([])for people in range(n + 1):
-1].append([])
dp[for mx_points in range(k + 1):
-1][-1].append(1 if total == 0 else 0)
dp[
for total in range(1, k + 1):
for people in range(1, n + 1):
for mx_points in range(1, k + 1):
= 0
dp[total][people][mx_points] for last in range(mx_points + 1):
if total - last < 0:
break
+= dp[total - last][people - 1][mx_points]
dp[total][people][mx_points] if dp[total][people][mx_points] >= mod:
-= mod
dp[total][people][mx_points]
= 0
ans for winner_points in range(1, k + 1):
+= dp[k - winner_points][n - 1][winner_points - 1]
ans if ans >= mod:
-= mod
ans
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) {
1 << '\n';
cout << 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 ¤t = dp[people][total];
current +=1] +
dp[people][total - 1][total] -
dp[people - 1][total - mx_points - 1] - mod : 0);
(total > mx_points ? dp[people -
current -= mod * (current >= mod);
current -= mod * (current >= mod);
}
}
1][k_limit];
ans += dp[n -
ans -= mod * (ans >= mod);
}
'\n';
cout << (ans * n) % mod <<
}
}
= 1000000007
mod
= int(input())
TC for _ in range(TC):
= list(map(int, input().split()))
n, k
if n == 1:
print(1)
continue
= [[-1 for j in range(k)] for i in range(n)]
dp = 0
ans for mx_points in range(k):
= k - mx_points - 1
k_limit for people in range(n):
for total in range(k_limit + 1):
= 1 if total == 0 else 0
dp[people][total] for people in range(1, n):
for total in range(1, k_limit + 1):
+= dp[people][total - 1] + dp[people - 1][total] - (dp[people - 1][total - mx_points - 1] if total > mx_points else 0)
dp[people][total] for i in range(2):
-= mod * (1 if dp[people][total] >= mod else 0)
dp[people][total] += dp[n - 1][k_limit]
ans -= mod * (1 if ans >= mod else 0)
ans 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ť.