6. Opäť sa hady hadiť budú vzorové riešenie

1 1 1

1

2 2 2

6

3 3 3

78

4 4 4

1428

5 5 5

34020

Hlavná myšlienka

Ak by sme s úlohou nevedeli nijako pohnúť, mohli by sme naprogramovať nejakú rekurziu, čo by skúšala všetky permutácie ukladania hadov do mriežky a mala by otrasnú časovú zložitosť. Skúsenejšiemu riešiteľovi by sa však mala táto úloha rýchlo odhaliť ako úloha na dynamické programovanie.

Teda namiesto toho, aby sme navštívili každé možné rozloženie hadov a zväčšili počítadlo riešení o jedna, budeme veľa rozložení charakterizovať určitým stavom, navštevovať iba tieto menej početné stavy a počítadlo tak zväčšovať o veľké množstva naraz.

Teraz by sme boli radi, keby sme vedeli všetky rozloženia mriežky nejako rozumne reprezentovať do čo najmenej stavov, aby sme mali čo najlepšiu časovú zložitosť.

Poďme do mriežky umiestňovať hadov. Robiť to len tak náhodne asi nie je veľmi rozumné, a teda sa rozhodnime, že ich budeme umiestňovať napríklad po riadkoch zdola nahor – teda pre každý riadok sa rozhodneme koľko a kam chceme hadov položiť a potom prejdeme na ďalší riadok. Vďaka tomuto sa vždy nachádzame v stave, kde všetky riadky, na ktoré sme sa doteraz pozreli, už nemusíme uvažovať a všetky, na ktoré sme sa ešte nepozreli, sú prázdne. Namiesto toho aby sme si teda pamätali celú tabuľku s pozíciami hadov, nám bude stačiť si pamätať, koľko hadov sme už umiestnili, koľko riadkov sme už naplnili (počet neumiestnených hadov a prázdnych riadkov je triviálne dopočítatelný) a počet hadov pre každý stĺpec.

Čo sa týka stĺpcov, môžeme si povšimnúť, že ak máme nejaké rozloženie hadov, na poradí stĺpcov veľmi nezáleží a ľubovoľné ich premiešanie je tiež valídne rozloženie. Preto je lepšia reprezentácia, kde si namiesto pamätania počtu hadov pre každý stĺpec pamätáme iba počet stĺpcov čo majú 0, 1 a 2 hady.

V tomto momente vieme teda stav reprezentovať piatimi číslami (počet umiestnených hadov, naplnených riadkov a stĺpcov s 0, 1 a 2 hadmi), čím by sme získali približne \(O(K N M^3)\) stavov. Toto je však stále omnoho viac, ako je potrebné na získanie 8 bodov. Našťastie by malo byť ľahké tento počet zredukovať. Totiž, počet stĺpcov s 0 a 1 hadmi sa dá ľahko vypočítať z ostatných hodnôt. Ak \(U\) je počet hadov, ktoré sme už umiestnili, a \(S_i\) je počet stĺpcov s \(i\) hadmi, tak \(S_1=U - 2S_2\) a \(S_0=M-(S_1+S_2)\). Zostáva nám teda iba \(O(K N M)\) stavov. Keďže \(K\) môže byť nanajvýš \(2 \cdot \min(N, M)\) (inak neexistuje valídne rozloženie), tak počet stavov je \(O(\min(N,M)^2 \cdot \max(N,M))\).

Samozrejme, existujú aj iné reprezentácie stavov, bolo by však zbytočné ich tu uvádzať.

Teraz treba nájsť spôsob, ako z aktuálneho stavu odvodiť ostatné, alebo naopak, ako z ostatných stavov odvodiť aktuálny. Ľahšie sa vysvetľuje tá druhá možnosť, takže spravme to. Povedzme, že chceme vyjadriť stav \(D[n][u][s_2]\), teda stav, kde sme už naplnili \(n\) riadkov, umiestnili \(u\) hadov a máme \(s_2\) stĺpcov s dvoma hadmi. Pripomínam, že z týchto troch informácií vieme dopočítať \(s_1\) a \(s_0\). Do tohoto stavu sme prišli z nejakého iného, v ktorom sme mali o jeden menej naplnených riadkov, tak, že sme do jedného riadku pridali nula až dvoch hadov. Každú z týchto troch možností vyriešime samostatne.

Ak sme sa v predchádzajúcom stave rozhodli uložiť \(0\) hadov, počet uložených hadov ani počet \(s_2\) sa nezmenil, teda sme do aktuálneho stavu iba pripočítali počet rozložení predchádzajúceho stavu. Teda \(D[n][u][s_2] \mathrel{{+}{=}} D[n-1][u][s_2]\).

Ak sme sa v predchádzajúcom stave rozhodli uložiť \(1\) hada, počet uložených hadov sa zvýšil o jedna a počet \(s_2\) sa buď zmenil alebo nezmenil, podľa toho, do ktorého stĺpca sme daného hada vložili. Ak sme ho vložili do stĺpca s \(0\) hadmi (ktorých je \(s_0\)) tak sa \(s_2\) nezmenilo. Ak sme ho vložili do stĺpca s jedným hadom (ktorých je \(s_1\)) tak sa \(s_2\) zvýšilo o \(1\). Teda \(D[n][u][s_2] \mathrel{{+}{=}} s_0 \cdot D[n-1][u-1][s_2] + s1 \cdot D[n-1][u-1][s_2-1]\).

Ak sme sa v predchádzajúcom stave rozhodli uložiť \(2\) hadov, počet uložených hadov sa zvýšil o dva a počet \(s_2\) sa znova mohol, ale nemusel, zmeniť. Tentoraz máme až \(3\) možnosti ako sme ich mohli uložiť:

1. oboch do nulového stĺpca – to môžeme spraviť \(s_0 (s_0-1) / 2\) spôsobmi
2. jedného do nulového a jedného do jednotkového stĺpca – to môžeme spraviť \(s_0 \cdot s_1\) spôsobmi
3. oboch do jednotkového stĺpca – to môžeme spraviť \(s1(s1-1) / 2\) spôsobmi

To, ako sa zmenilo \(s_2\) je ľahké odvodiť. Dostávame teda \(D[n][u][s_2] \mathrel{{+}{=}} (s_0 (s_0-1) / 2) \cdot D[n-1][u-2][s_2] + (s_0 \cdot s_1) \cdot D[n-1][u-2][s_2-1] \ + (s_1 (s_1-1) / 2) \cdot D[n-1][u-2][s_2-2]\).

Zostáva nám iba pridať modulovanie a ošetriť, aby sme nepoužívali záporné indexy do polí. Začíname s informáciou \(D[0][0][0] = 1\) a zvyšok tabuľky už vieme potom dopočítať. Vypočítanie ľubovoľného indexu trvá \(O(1)\) a teda časová aj pamäťová zložitosť je \(O(\min(N,M)^2 \cdot \max(N,M))\).

Posledná vec, ktorú si môžeme všimnúť, je, že výpočet \(D[n]\) závisí iba od \(D[n-1]\). Teda ak budeme tabuľku počítať v rozumnom poradí (najprv všetky hodnoty pre určité \(n\), až potom pre \(n+1\)), môžeme na \(D[n-2]\) vždy zabudnúť a znížiť tak pamäťovú zložitosť na \(O(M \cdot \min(N,M))\). A keďže vieme, že počet riešení je rovnaký pre tabuľky rozmerov \(N \times M\) a \(M \times N\), tak môžeme \(N\) a \(M\) vymeniť tak, aby nám to vyhovovalo a získať pamäťovú zložitosť \(O(min(N,M)^2)\).

Riešenie tejto úlohy obsahovalo veľa pozorovaní a trikov. Veľa z nich však nebolo nutných (napríklad zníženie pamäťovej zložitosti), alebo sa dali získať čiastkové body ak ste ich nenašli.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll MOD = 1e9 + 7;

int main() {
    ll N, M, K;
    cin >> N >> M >> K;

    if(N > M) // aj ked to nie je nutne, je fajn mat v zivote urcite istoty
        swap(N, M); // napriklad ze N<M
    if(K > N * 2)
        return 0;
    
    vector<vector<vector<ll>>> D(N+1, vector<vector<ll>>(K+1, vector<ll>(M+3, 0)));
    D[0][0][0] = 1;
    for(ll n=0; n<N; ++n) { // ideme po N-1, v n=N uz budu vypocitane vysledky
        for(ll k=0; k<=K; ++k) {
            for(ll m2=0; m2<=M; ++m2) {
                // mi je pocet stlpcov co maju i policok obsadenych - potom plati:
                // m0+m1+m2 == M, 0*m0+1*m1+2*m2 == k
                ll &curr = D[n][k][m2];
                curr %= MOD; // vzdy sa snazme modulovat co najmenej
                // kedze modulo je pomale, teda namiesto toho aby sme nizsie
                // modulovali 6 krat ked pripocitavame do D, staci modulovat
                // iba raz ked chceme vyslednu hodnotu pouzit

                ll m1 = k - m2*2;
                ll m0 = M - m2 - m1;
                ll zostava = K - k;
                
                // na rozdiel od slovneho vozraku tu hodnoty tlacime namiesto
                // tahania. myslienkovo v tom nie je velky rozdiel, len sa mi
                // jedna vec lahsie vysvetlovala a druha lahsie programovala
                if(zostava >= 0) {
                    D[n+1][k][m2] += curr;
                }
                if(zostava >= 1) {
                    D[n+1][k+1][m2+1] += curr * m1;
                    D[n+1][k+1][m2] += curr * m0;
                }
                if(zostava >= 2) {
                    D[n+1][k+2][m2+2] += curr * m1 * (m1 - 1) / 2;
                    D[n+1][k+2][m2+1] += curr * m1 * m0;
                    D[n+1][k+2][m2] += curr * m0 * (m0 - 1) / 2;
                }
            }
        }
    }
    
    ll res=0;
    for(ll x: D.back().back())
        res = (res + x) % MOD;
    cout << res << endl;
}

# toto je vpodstate bezduchy prepis c++ kodu do pythonu
# ak viete c++ tak si skor precitajte to, su tam komentare navyse
# ale aj ked c++ neviete tak ho celkom iste bez vacsich problemov pochopite

MOD = 10**9+7

N, M, K = map(int, input().split())

if N > M:
    N, M = M, N
if K > N * 2:
    return 0

D = [[[0 for m in range(M+3)] for k in range(K+1)] for n in range(N+1)]
D[0][0][0] = 1
for n in range(N):
    for k in range(K+1):
        for m2 in range(M+1):
            # m0+m1+m2 == M, 0*m0+1*m1+2*m2 == k
            D[n][k][m2] %= MOD
            curr = D[n][k][m2]

            m1 = k - m2*2
            m0 = M - m2 - m1
            left = K - k
            
            if left >= 0:
                D[n+1][k][m2] += curr
            if left >= 1:
                D[n+1][k+1][m2+1] += curr * m1
                D[n+1][k+1][m2] += curr * m0
            if left >= 2:
                D[n+1][k+2][m2+2] += curr * m1 * (m1 - 1) // 2
                D[n+1][k+2][m2+1] += curr * m1 * m0
                D[n+1][k+2][m2] += curr * m0 * (m0 - 1) // 2
res=0
for x in D[-1][-1]:
    res = (res + x) % MOD

print(res)