Zadanie
Byť vedúci na sústredení je naozaj super. Hlavne preto, že máte na starosti 32 účastníkov, ktorí vás musia poslúchať bez ohľadu na to, čo im prikážete urobiť. A tak sa noví vedúci mstia ďalšej generácii za krivdy, ktoré im boli spôsobené, keď boli ešte účastníkmi. Takto potom tento kolobeh pokračuje donekonečna
Emo si tiež živo spomína na príkoria, ktoré podstupoval na sústredeniach. Najviac nemal rád rozcvičky, lebo ho vedúci vytiahli z postele a nútili behať, skákať a drepovať. Preto sa rozhodol, že teraz donúti účastníkov drepovať on. Vymyslel si na to vskutku zaujímavý spôsob.
Najskôr všetkých účastníkov usporiadal do \(s\) zástupov. V každom z nich bolo \(r\) účastníkov. Vytvoril tak obdĺžnik veľkosti \(r \times s\). Následne si opakovane vyberal riadok alebo stĺpec tohto obdĺžnika a nútil účastníkov v danom riadku alebo stĺpci spraviť poldrep. To znamená, že ak účastník stál, tak si musel čupnúť a ak čupel, tak sa musel postaviť.
Ak napríklad ukázal na tretí stĺpec, všetci účastníci v treťom zástupe si museli čupnúť a ostatní ostali stáť. Ak potom ukázal na druhý riadok, tak všetci účastníci v druhom riadku si museli čupnúť, okrem účastníka, ktorý bol v druhom riadku a treťom stĺpci. Ten totiž už čupel a preto sa musel postaviť.
Keď to Ema prestalo baviť1, pustil účastníkov na raňajky. Ešte pred tým si však zapamätal, že na konci čupelo presne \(k\) účastníkov. Keď potom prišiel na raňajky, sadol si vedľa Miša, ktorému vysvetlil, čo robil. Miša táto hra zaujala a chcel vedieť, koľkými spôsobmi vedel Emo docieliť stav, pri ktorom na konci čupelo \(k\) ľudí. Nevedel si s tým však poradiť, preto poprosil Ema, aby mu povedal ešte niečo viac. Emo mu preto prezradil, že keď si vyberal stĺpce a riadky, ktoré majú spraviť poldrep, riadok si vybral \(p_r\)-krát a stĺpec \(p_s\)-krát.
To už Mišovi na vyriešenie úlohy stačilo a povedal si, že vám takúto úlohu zadá, aby ste sa potrápili aj vy.
Úloha
Na začiatku mal Emo stojacich účastníkov, ktorí boli rozdelení do obdĺžnika s \(r\) riadkami a \(s\) stĺpcami. Následne Emo určoval niektoré riadky alebo stĺpce a účastníci v nich museli zmeniť svoj stav – ak stáli, museli si čupnúť, ak čupeli, museli sa postaviť.
Vypočítajte, koľkými spôsobmi mohol určiť \(p_r\) riadkov a \(p_s\) stĺpcov tak, aby na konci ostalo \(k\) čupiacich ľudí. Dve možnosti považujeme za rôzne, ak existuje riadok alebo stĺpec, ktorý bol vybratý v oboch možnostiach rôzny počet krát. Nezáleží nám teda na poradí, v akom Emo riadky a stĺpce určoval.
Keďže výsledok môže byť príliš veľký, vypíšte iba jeho zvyšok po delení číslom \(555\,555\,555\).
Formát vstupu
Vstup obsahuje päť medzerou oddelených čísel \(r\), \(s\), \(p_r\), \(p_s\) a \(k\) – počet riadkov a stĺpcov obdĺžnika, počty vybratí niektorého riadka, počty vybratí niektorého stĺpca a počet účastníkov, ktorí na konci ostali čupieť.
Pre tieto hodnoty platí, že \(1 \leq r,s \leq 1\,500\), \(0 \leq p_r,p_s \leq 1\,500\) a \(0 \leq k \leq rs\).
Naviac, v prvej sade vstupov platí, že \(1 \leq r,s,p_r,p_s \leq 10\), v druhej sade vstupov platí, že \(1 \leq r,s \leq 20\) a v tretej sade platí, že \(1 \leq r,s,p_r,p_s \leq 100\).
Formát výstupu
Vypíšte jedno číslo – počet možností, ktorými vieme určiť \(p_r\) riadkov a \(p_s\) stĺpcov tak, aby ostalo čupieť \(k\) účastníkov. Keďže toto číslo môže byť príliš veľké, vypíšte iba jeho zvyšok po delení číslom \(555\,555\,555\).
Príklad
Input:
2 2 2 2 4
Output:
4
V dvoch možnostiach vybral Emo oba riadky a jeden zo stĺpcov dvakrát. V druhých dvoch možnostiach vybral oba stĺpce a jeden z riadkov dvakrát.
Input:
2 2 0 0 1
Output:
0
Ak Emo nevybral žiaden riadok ani stĺpec, nie je možné aby niekto čupel.
Input:
8 4 12 3 8
Output:
27600
Po asi hodine a pol.↩
Začnime tým, že si zopakujeme, o čom bolo zadanie a zavedieme trochu iné pojmy, ktoré budeme používať na popis situácie. V zadaní sme mali mriežku \(r \times s\), v ktorej stáli účastníci. Každý účastník buď stál alebo čupel. Namiesto účastníkov však vyplňme našu mriežku 0 a 1. 0 bude predstavovať stojaceho účastníka a 1 čupiaceho.
Emo potom určoval riadky a stĺpce tejto mriežky a účastníci v príslušnom riadku alebo stĺpci si museli čupnúť ak stáli a naopak. Pri použití 0 a 1 to znamená, že vždy, keď určíme nejaký stĺpec alebo riadok, tak sa v ňom všetky 0 zmenia na 1 a naopak. Vieme, že Emo určil dokopy \(p_r\) riadkov a \(p_s\) stĺpcov a na konci bolo v mriežke \(k\) čupiacich účastníkov – teda \(k\) hodnôt 1.
Našou úlohou bolo vypočítať, koľkými možnosťami mohol za uvedených podmienok tento výsledok dosiahnuť. Už v zadaní je napísané, že pri počítaní možností nám nezáleží na tom, v akom poradí Emo riadky a stĺpce určoval. Uvedomme si, že táto podmienka je rozumná, lebo poradie nezmení to, ako vyzerá výsledná mriežka a koľko jednotiek obsahuje.
Pozorovanie
Čo teda ovplyvňuje to, ako vyzerá mriežka na konci? Kedy bude v \(i\)-tom riadku a \(j\)-tom stĺpci 1 a kedy tam bude 0?
Je jasné, že vybratie iného ako \(i\)-teho riadku alebo \(j\)-teho stĺpca nijak neovplyvňuje číslo na tomto políčku. Taktiež vieme, že na začiatku bola na tomto políčku 0. Vždy keď vyberieme \(i\)-ty riadok alebo \(j\)-ty stĺpec sa táto hodnota zmení na opačnú. Ak si označíme hodnotu \(r_i\) počet vybraní \(i\)-teho riadku a \(s_j\) počet vybraní \(j\)-teho stĺpca, tak ľahko nahliadneme, že hodnota na tomto políčku bude na konci \(r_i + s_j \mod 2\). Teda parita počtu vybratí, ktoré ovplyvnili toto políčko. To nás vedie k veľmi zaujímavej úvahe. Zjavne je jedno, koľkokrát určíme niektorý riadok alebo stĺpec, dôležitá je len parita tohto počtu určení.
Poďme však s touto úvahou ešte ďalej. Nech bolo \(x_r\) riadkov a \(x_s\) stĺpcov vybraných nepárny počet krát. Koľko 1 bude vo výslednej mriežke? Zjavne na miestach kde sa pretína takýto nepárny riadok a stĺpec bude 0, lebo tieto dve vybratia sa anulujú. Takže 1 bude len na miestach, kde sa pretína nepárny riadok s párnym stĺpcom alebo naopak. Počet 1 vo výslednej mriežke teda bude \(x_r \cdot (s-x_s) + (r-x_r) \cdot x_s\). Ak si teda určíme koľko riadkov a koľko stĺpcov bolo vybraných nepárny počet krát, vieme ľahko overiť, či takéto vybratie viedlo ku \(k\) jednotkám vo výslednej mriežke.
Avšak, všimnime si, že nás nezaujíma ani to, ktoré riadky a stĺpce to budú. Jediný dôležitý je ich počet. No a vzhľadom na veľkosť vstupu nie je problém vyskúšať všetky kombinácie počtov nepárnych riadkov a stĺpcov a zistiť, či je takáto kombinácia (dvojica – počet nepárnych riadkov, počet nepárnych stĺpcov) vyhovujúca a vytvorí potrebný počet jednotiek.
To, čo sme spravili doteraz nám však predsa vôbec nepomáha. Veď stále nevieme, koľko bolo všetkých možností. Získali sme však dôležitú vec. Všetky výsledné možnosti sme si rozdelili do pomerne málo (najviac \((r+1) \cdot (s+1)\)) skupín podľa počtov nepárnych riadkov a stĺpcov. Pritom každá možnosť patrí do práve jednej takejto skupiny – stačí sa pozrieť, koľko jej riadkov a koľko jej stĺpcov bolo vybraných nepárny počet krát. Ak sa teda vrátime späť a podarí sa nám rýchlo vypočítať, koľko výsledných možností leží v danej skupine budeme vedieť pomerne rýchlo zistiť výsledok. Jednoducho sčítame veľkosti správnych skupín – tých, ktoré vedú k vytvoreniu \(k\) jednotiek.
Počítanie veľkosti jednej skupiny
Úloha sa teda zmenila: Koľko možností vybratia \(p_r\) riadkov a \(p_s\) stĺpcov vedie k tomu, že \(x_r\) riadkov a \(x_s\) stĺpcov vyberieme nepárny počet krát?
Pri tomto počítaní musíme postupne započítať všetko, čo sme zanedbali. To znamená výber konkrétnych \(x_r\) riadkov (a to isté pre stĺpce), ktoré majú byť vybrané nepárny počet krát a samotné počty vybratí každého riadku (resp. stĺpca).
Začnime tým prvým. Ak máme hodnotu \(x_r\), musíme započítať všetky možnosti, kde je práve \(x_r\) riadkov vybraných nepárny počet krát. Ak ste už počuli o kombinačných číslach, tak by vám malo byť jasné, že tento počet možností je práve \({r \choose x_r}\). Lebo práve kombinačné číslo \(r\) nad \(x_r\) vyjadruje to, koľkými možnosťami vieme z \(r\) vecí (riadkov) vybrať \(x_r\) (tých nepárnych riadkov). Pre ľahší zápis zapisujme toto číslo \(P(r, x_r)\).
Ak ste o kombinačných číslach ešte nepočuli, nič si z toho nerobte. Za chvíľu sa dostaneme k tomu, ako ich počítať bez ohľadu na to, či viete, čo to je. Zatiaľ však akceptujte ich existenciu a to, že sú presne hodnotou, ktorú hľadáme.
Ostáva nám ešte druhý krok zovšeobecnenia. Aj keď sme priradili každému riadku paritu, musíme túto výslednú paritu dosiahnuť nejakým konkrétnym vybratím týchto riadkov. Koľko je však týchto možností? Zjavne, každý z nepárnych riadkov musel byť vybraný aspoň raz. To znamená, že nám ostáva rozdeliť \(p_r - x_r\) vybraní. Tieto vybratia však musia ísť vždy v páre. Jedno vybratie by totiž zmenilo paritu a to nechceme. Takže ak sa rozhodneme priradiť niektorému riadku ďalšie vybratie, musíme to spraviť rovno dvakrát. Máme teda \(\frac{p_r-x_r}{2}\) párov vybratí a každý pár musíme priradiť niektorému riadku.
Opäť dostávame pomerne známu hodnotu – počet kombinácií s opakovaním \(C(r, (p_r-x_r)/2)\). Keďže nám nezáleží na poradí, tak z \(r\) riadkov chceme vybrať \((p_r-x_r)/2\), niektoré riadky však môžeme aj opakovať – priradiť viacerým párom. Opakovanie znamená, že danému riadku nepriradíme len 2 vybratia (1 pár), ale 4, 6…
Naviac, pre kombinácie s opakovaním platí veľmi užitočná vlastnosť, že \(C(n, k) = P(n+k-1, k)\). To znamená, že ak vieme počítať kombinácie bez opakovania, vieme počítať aj tie s opakovaním.
Ak si teda zoberieme hodnoty \(x_r\) a \(x_s\) a tieto dve hodnoty vedú k požadovanému výsledku – vytvoria \(k\) jednotiek a taktiež \(x_r\) má rovnakú paritu ako \(p_r\) (párnym počtom vybratí riadku nemôžem vytvoriť nepárny počet nepárny počet krát vybraných riadkov) a \(x_s\) má rovnakú paritu ako \(p_s\), tak počet možností v takejto množine spočítame ako \(P(r, x_r) \cdot P(s, x_s) \cdot C(r, (p_r-x_r)/2) \cdot C(s, (p_s-x_s)/2)\).
Riešenie
Na vypočítanie hodnôt \(P(a,b)\) a \(C(a,b)\) použijeme Pascalov trojuholník. Ten si na začiatku behu programu spočítame pre dostatočne veľké hodnoty, teda prvých \(m\) riadkov, kde \(m = max(2r, 2s, 2p_r, 2p_s)\). Potom už len pre každú z \((s+1)\cdot(r+1)\) skupín v konštantnom čase overíme, či vytvára \(k\) jednotiek a v konštantnom čase spočítame (pomocou Pascalovho trojuholníka), koľko možností patrí do danej skupiny. Celkovo tak dostaneme riešenie so zložitosťou \(O(m^2 + r\cdot s) = O(m^2)\).
Kombinačné čísla
Možno si teraz hovoríte, že táto úloha je nefér pre niekoho, kto nikdy nepočul o kombinačných číslach. No aj keď je pre niekoho takého rozhodne ťažšia, zďaleka nie je neriešiteľná. Zabudnime preto na to, že existujú nejaké kombinačné čísla a riešme úlohu: Koľkými možnosťami vieme vybrať \(k\) prvkov z \(n\) možných, ak nám nezáleží na poradí a prvky sa nemôžu pri výbere opakovať?
Na začiatok môžeme vyriešiť nejaké jednoduché podproblémy. Napríklad ak je \(k = n\) tak zjavne máme jedinú možnosť. Takisto ak je \(k=0\), tak ostáva jediná možnosť, nič nevybrať. Ak je \(k=1\), tak možností máme \(n\), môžeme totiž vybrať ľubovoľný prvok. Zaujímavý je tiež prípad, keď \(k > n\). V takom prípade je odpoveď 0, keďže neexistuje spôsob ako z \(n\) prvkov vybrať \(k\).
Pozrime sa teraz na všeobecný prípad, keď máme \(n\) vecí, z ktorých chceme \(k\) vybrať a \(k \geq 1\). Zoberme si teraz ľubovoľný z \(n\) prvkov, označme si ho \(x\). Keďže nám nezáleží na poradí vyberania, jediné čo sa musíme pýtať je, či tento prvok vyberieme alebo nie. Všetky možnosti sa teda rozdelia na dve skupiny – možnosti, v ktorých prvok \(x\) vyberieme a možnosti, kde \(x\) nevyberieme.
Ak teda chceme zistiť hodnotu \(P(n,k)\) vedeli by sme to vypočítať ako súčet možností v týchto dvoch skupinách. Skúsme teda vypočítať, koľko je takých možností, v ktorých \(x\) vyberieme. Tento prvok už použiť nemôžeme, takže nám ostáva \(n-1\) prvkov. Z nich ale potrebujeme vybrať už len \(k-1\) prvkov, keďže sme už vybrali prvok \(x\). Táto hodnota je preto \(P(n-1, k-1)\). A podobnú vlastnosť nájdeme aj v prípade, keď prvok \(x\) nevyberieme. Ostáva nám už len \(n-1\) prvkov (lebo o prvku \(x\) sme sa už rozhodli, že ho neberieme), z ktorých musíme vybrať ešte \(k\). Takže máme hodnotu \(P(n-1, k)\).
Dostávame vzorec:
\[P(n, k) = P(n-1, k) + P(n-1, k-1)\]
Toto je pomerne dôležitý kombinatorický vzorec, ktorého aplikáciou vzniká napríklad Pascalov trojuholník. A práve tento trojuholník je to, čo chceme počítať. Postupne budeme počítať všetky hodnoty \(P(n,k)\). Keďže na vypočítanie \(P(n,k)\) potrebujeme hodnoty s menším \(n\), budeme tieto hodnoty počítať od najmenších hodnôt \(n\).
Na začiatku vieme, že \(P(0, 0) = 1\). Následne budeme počítať všetky kombinačné čísla s \(n=1\). Aby sme sa nesnažili vyberať záporný počet prvkov, tak si určíme, že \(P(1,0) = 1\) a zvyšné hodnoty vypočítame vzorcom uvedeným vyššie. Toto všetko si budeme značiť do tabuľky, kde \(n\) je číslo riadku a \(k\) číslo stĺpca.
Po vypočítaní všetkých hodnôt pre \(n=1\) sa presunieme do riadku s \(n=2\) atď. Pričom vždy si v riadku pevne určíme hodnotu \(P(n,0) = 1\) a potom na výpočet všetkých \(1 \leq k \leq n\) použijeme odvodený vzorec. A keďže hodnoty, ktoré potrebujeme vo vzorci, už máme vypočítané, vypočítanie novej hodnoty nám zaberie konštantný čas. Časová zložitosť výpočtu Pascalovho trojuholníka je preto \(O(n^2)\).
Ešte sme však nevyriešili, ako počítať kombinácie s opakovaním. Hlavne ak nepoznáme vzorec na prevod na kombinácie bez opakovania. Žiaden strach, použijeme úplne rovnakú úvahu. Naša úloha znie: Koľkými spôsobmi viem z \(n\) prvkov vybrať \(k\), ak nám nezáleží na poradí, ale niektoré prvky môžeme vybrať aj viackrát.
Opäť si zoberieme prvok \(x\), o ktorom sa budeme rozhodovať, či ho zoberieme alebo nie. Ak sa však rozhodneme, že prvok \(x\) nevyberieme, už nemáme možnosť ho zobrať neskôr. Ak ho chceme vybrať, hoci aj viackrát, musíme to spraviť teraz.
Ak teda prvok \(x\) nezoberieme, tak ako pred tým nám ostane \(n-1\) prvkov, z ktorých musíme vybrať \(k\). Ak však prvok \(x\) vyberieme, budeme vyberať tiež \(k-1\) prvkov, na výber však budeme mať všetkých \(n\) prvkov, teda sa opäť môžeme rozhodnúť zobrať prvok \(x\). To nám zaručí, že prvky vieme vyberať aj viac ako raz. A takisto nám to odvádza vzorec:
\[C(n, k) = C(n, k-1) + C(n-1, k-1)\]
Použitím rovnakej metódy ako pri počítaní Pascalovho trojuholníka vieme vypočítať aj tieto hodnoty s časovou zložitosťou \(O(n^2)\). A nepotrebovali sme poznať zložité vzorce, stačilo vedieť správne použiť metódy dynamického programovania.
Posledná vec, ktorú treba spomenúť je, prečo sme na výpočet nepoužívali vzorec \({n \choose k} = \frac{n!}{k!(n-k)!}\). Problémom je, že výsledné číslo musíme modulovať, vrátiť len jeho zvyšok po delení \(555\,555\,555\). Ak by sme chceli teda používať faktoriály, tak by sme si museli vypočítať ich hodnoty modulo toto číslo, keďže \(1500!\) sa nám do žiadnej číselnej premennej nezmestí (už s 20! by sme mali problém).
Problém ale potom nastáva pri delení. Modulo síce pekne funguje pri násobení alebo sčítaní a napríklad \(a\cdot b \pmod{m} = (a \pmod{m})\cdot (b \pmod{m})\pmod{m}\) je správna rovnica, pre delenie takáto rovnica neplatí. Použítím delenia by sme preto dostali nesprávne čísla.
#include <cstdio>
#define MOD 555555555
using namespace std;
typedef long long ll;
ll P[2000][2000];
ll C[2000][2000];
int count( ll H, ll W, int Rcount, int Ccount, ll k ) {
for(int i=0; i<1750; i++) P[i][0]=1;
for(int i=1; i<1700; i++)
for(int j=1; j<=i; j++)
P[i][j] = (P[i-1][j] + P[i-1][j-1]) % MOD;
for(int i=0; i<1750; i++){
C[i][0]=1;
C[1][i]=1;
}
for(int i=2; i<1700; i++)
for(int j=1; j<1700; j++)
C[i][j] = (C[i][j-1] + C[i-1][j]) % MOD;
ll vysledok = 0;
for(int i=0; i<=H; i++)
for(int j=0; j<=W; j++) {
ll pocet_jednotiek = (ll)j*H+(ll)i*W-2ll*(ll)i*(ll)j;
if(pocet_jednotiek==k && i<=Rcount && j<=Ccount && i%2==Rcount%2 && j%2==Ccount%2) {
ll poc=P[W][j]*P[H][i]; poc%=MOD;
poc*=C[W][(Ccount-j)/2]; poc%=MOD;
poc*=C[H][(Rcount-i)/2]; poc%=MOD;
vysledok += poc; vysledok %= MOD;
}
}
return vysledok;
}
int main() {
ll r, s, k;
int pr, ps;
scanf(" %lld %lld %d %d %lld ", &r, &s, &pr, &ps, &k);
printf("%d\n", count(r, s, pr, ps, k));
}
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ť.