6. Odplata drepovaním vzorové riešenie

2 2 2 2 4

4

2 2 0 0 1

0

8 4 12 3 8

27600

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));
}