6. Váľanie hypergúľ vzorové riešenie

4
1 0
1 2
2 1
3 4

1
2
0
90

Samozrejme pre nepárne časy nikdy neexistuje žiadna cesta (trojitý zápor) a teda otázky s nepárnymi časmi už ďalej nebudeme rozoberať.

Prvé dve sady

Na prejdenie prvej sady nám stačí pre každú otázku simulovať pohyb larvy backtrackingom. Nech \(D\) je počet dimenzií a \(C\) je počet sekúnd pohybu larvy, teda počet krokov čo má spraviť. Na začiatku je pozícia larvy zoznam \(D\) núl. V každom kroku rekurzie sa skúsime pohnúť pre každú dimenziu do každého z dvoch smerov. V rekurzii hĺbky \(C\) sa pozrieme, či je pozícia znova \(D\) núl a ak áno, výsledok zvýšime o jedna. Pri backtrackingu sa veľmi oplatí prerušiť rekurziu ak vieme, že aktuálny stav určite nevedie k výsledku. V tejto úlohe je to napríklad ak je vzdialenosť od začiatku väčšia ako čas čo nám zostáva. Časová zložitosť pre riešenie bez rušenia rekurzie je \(O(Q \cdot (2D)^C)\).

Riešenie druhej sady je podobné, ale využije šikovnejšiu reprezentáciu pozície larvy. Vo výsledku nás nezaujíma, či sa larva najprv pohla v smere prvej či druhej dimenzie. Pozíciu vieme reprezentovať iba ako pole \(P\), kde na \(i\)-tom indexe bude počet dimenzií, pre ktoré sme vo vzdialenosti \(i\). Toto nám samo o sebe veľmi nepomáha – musíme ešte zmeniť ako sa vnárame do rekurzie. Namiesto toho aby sme si vybrali jednu dimenziu v ktorej sa pohneme, vyberieme si skupinu dimenzií s rovnakou vzdialenosťou (teda jeden index v \(P\)). Môžeme si všimnúť, že nech sa pohneme v ľubovoľnej z nich, následná reprezentácia pozície larvy bude rovnaká. Teda vieme vykonať vnáranie sa do rekurzie iba raz, a výsledok vynásobiť počtom dimenzií v tejto skupine. Horný odhad časovej zložitosti pre riešenie bez rušenia rekurzie je \(O(Q \cdot C^C)\), keďže teraz v rekurzií skúšame \(2\) smery pre \(C/2\) skupín (vzdialenosť v ľubovoľnej dimenzií nemôže byť viac, inak by sme sa nestihli vrátiť). Môžeme si všimnúť, že ide naozaj iba o horný odhad, keďže \(100 \cdot 15^{15}\) by určite neprešlo v časovom limite.

Obe riešenia predpokladali, že si pri rekurzií budeme stavové pole posielať ako referenciu, lebo to by sme vždy mali robiť. V tom prípade budú pamäťové zložitosti iba lineárne závislé od veľkosti týchto poli, teda \(O(D)\) pre prvú a \(O(C)\) pre druhú sadu.

def rekurzia(pocet, zostava):
    # ak je nasa vzdialenost od zaciatku vacsia ako cas
    # co nam zostava tak mozeme ukoncit rekurziu
    if sum(map(abs, pocet)) > zostava:
        return 0

    if zostava == 0:
        return 0 if any(pocet) else 1

    res = 0
    for dimenzia in range(len(pocet)):
        for smer in (-1, 1):
            pocet[dimenzia] += smer
            res += rekurzia(pocet, zostava-1)
            pocet[dimenzia] -= smer

    return res

G = int(input())
for i in range(G):
    d, c = map(int, input().split())
    if c % 2:
        print(0)
        continue
    pocet = [0] * d
    print(rekurzia(pocet, c))

Posledná sada

Pozrime sa na limity vstupov. \(G\) je veľké. Nie je dobré počítať odpoveď pre každú otázku nanovo. Nerobme to. Niečo si predpočítajme. Čo ak máme odpoveď pre každý čas menší ako \(C\) pre každú dimenziu menšiu ako \(D\)? Vieme z týchto informácií niečo vypočítať? Možno \(C+2\) pre každé \(D\), možno \(D+1\) pre každé \(C\)? Ukážeme si to druhé z nich.

Najprv si ale predstavme ako vyzerá nejaká valídna trasa: Ak sa larva pohne v určitej dimenzií niektorým smerom, bude sa niekedy neskôr musieť pohnúť opačným. Teda trasu dĺžky \(c\) v \(d\) dimenziách si vieme predstaviť ako postupnosť \(c\) Jahodových a Karamelových čísel od \(1\) po \(d\) (kde Jahodové čísla reprezentujú opačný pohyb voči Karamelovým), ktoré vieme rozdeliť do Jahodovo-Karamelových dvojíc, kde čísla v rámci dvojice sú si rovné.

Naspäť k počítaniu. Majme výsledok \(V(c,\,d)\) vypočítaný pre každú dvojicu \((c,\,d)\), kde \(c \leq C\) je dĺžka trasy a \(d \leq D\) je počet dimenzií ktoré môžeme na danej trase použiť. Potom vieme vypočítať aj \(V(c,\,D+1)\), pre ľubovoľné \(c \leq C\). Výsledok \(V(c,\,D+1)\) je počet postupnosti Jahodových a Karamelových čísel od \(1\) po \(D+1\) s hore uvedenými vlastnosťami. Každú takúto postupnosť vieme vytvoriť z postupnosti Jahodových a Kararamelových čísel od \(1\) po \(D\), do ktorej pridáme niekoľko Jahodových a Karamelových čísel s hodnotou \(D+1\). To koľko čísel \(D+1\) pridáme nám určuje, akú dĺžku mala postupnosť pred tým ako sme ich pridali. Teda ak pridáme \(x\) čísel, pridávame ich do postupnosti s parametrami \((c-x,\,D)\), ktorých vieme že je \(V(c-x,\,D)\).

Potrebujeme ešte zistiť, koľkými spôsobmi vieme týchto \(x\) čísel do postupnosti pridať. Máme \(x\) čísel, všetky sú od seba na nerozoznanie. Potrebujeme ich ochutiť tak, aby polovica z nich bola Jahodová a polovica Karamelová (aby sme vo výsledku skončili v dimenzií \(D+1\) na pozícii 0). Teda potrebujeme vybrať \(x/2\) prvkov z \(x\), čo vieme spraviť \(\binom{x}{x/2}\) spôsobmi. Teraz máme postupnosť \(x\) ochutených čísel s hodnotou \(D+1\) a postupnosť \(c-x\) ochutených čísel s hodnotami od \(1\) po \(D\) a chceme zistiť, koľkými spôsobmi ich vieme skombinovať do jednej. Výsledná postupnosť bude mať \(c\) prvkov a ak vyberieme na ktorých pozíciách budú čísla s hodnotou \(D+1\), jednoznačne to určí pozíciu zvyšných \(c-x\) čísel. Vidíme teda, že to vieme spraviť \(\binom{c}{x}\) spôsobmi.

Keďže počet postupností s parametrami \((c-x,\,D)\), počet ochutení a počet premiešaní daných dvoch postupností sú nezávislé operácie, počet postupností s parametrami \((c,\,D+1)\) v ktorých má \(x\) čísel hodnotu \(D+1\) bude súčinom týchto troch čísel. Nakoniec počet postupností s parametrami \((c,\,D+1)\) bez obmedzenia na \(x\) bude súčet výsledkov pre každé \(x\) od \(0\) po \(c\) vrátane. Výsledok teda vieme zapísať ako: \(V(c,\,D+1) = \sum_{x=0}^{c}{V(c-x,\,D) \cdot \binom{x}{x/2} \cdot \binom{c}{x}}\)

Hodnoty \(V(c,\,0)\) sú triviálne (pre \(c=0\) je to \(1\), pre ostatné \(0\)). Postupne budeme zvyšovať \(d\) pre ktoré vždy pre všetky \(c\) vypočítame \(V(c,\,d)\). Toto spravíme pre všetky \(c\) a \(d\) potrebné na zodpovedanie všetkých otázok na vstupe.

Všetko čo sme tu vymysleli by však bolo celkom premárnené ak by sme taktiež nevedeli rýchlo počítať \(\binom{y}{x}\). To vieme robiť veľa rôznymi spôsobmi – najjednoduchším je predpočítanie si Pascalovho trojuholníku, ale dá sa aj predpočítanie faktoriálov a ich inverzov pre modulo alebo vypočítanie podielu ako rozdiel množín faktorizácie faktoriálov.

Časová zložitosť tohoto riešenia je \(O(Q + C^2 \cdot D)\), keďže predpočítavame tabuľku s rozmermi \(C \times D\) s časovou zložitosťou \(O(C)\) pre každý prvok. Pamäťová zložitosť bude \(O(C \cdot D)\), alebo \(O(Q + C \cdot D)\) ak sa rozhodneme najprv nájsť maximálne hodnoty \(C\) a \(D\) na vstupe a nemuseli tak počítať prebytočné masívnu tabuľku.

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

using ll = long long;

int main() {
    const ll MOD = 1e9 + 7;

    ll G;
    cin >> G;

    vector<pair<ll, ll>> Gulky(G);
    ll maxD=0, maxC=0;
    for(int i=0; i<G; ++i) {
        cin >> Gulky[i].first >> Gulky[i].second;
        maxD = max(maxD, Gulky[i].first);
        maxC = max(maxC, Gulky[i].second);

    }
    ++maxD, ++maxC;

    // predpocitanie kombinacnych cisel pomocou Pascalovho trojuholnika
    vector<vector<ll>> nCr(maxC, vector<ll>(maxC, 0));
    nCr[0][0] = 1;
    for(int n=1; n<maxC; ++n) {
        nCr[n][0] = nCr[n][n] = 1;
        for(int r=1; r<n; ++r) {
            nCr[n][r] = (nCr[n-1][r-1] + nCr[n-1][r]) % MOD;
        }
    }

    vector<vector<ll>> RES(maxD, vector<ll>(maxC, 0));
    for(int d=0; d<maxD; ++d) // vieme ze odpoved pre c=0 je vzdy 1
        RES[d][0] = 1;
    for(int d=1; d<maxD; ++d) {
        for(int c=2; c<maxC; c+=2) {
            for(int pridame=0; pridame<=c; pridame+=2) {
                ll pocet_v_menej_dimenziach = RES[d-1][c-pridame];
                ll pozicie_pridanych = nCr[c][pridame];
                ll ochutenie_pridanych = nCr[pridame][pridame/2];
                ll sucin = ((pocet_v_menej_dimenziach * pozicie_pridanych) % MOD
                            * ochutenie_pridanych) % MOD;
                RES[d][c] = (RES[d][c] + sucin) % MOD;
            }
        }
    }

    for(pair<ll, ll> p: Gulky)
        cout << RES[p.first][p.second] << '\n';
}

MOD = 10**9 + 7

G = int(input())
Gulky = [list(map(int, input().split())) for i in range(G)]
maxD, maxC = [max(map(lambda x: x[i], Gulky))+1 for i in range(2)]

nCr = [[0 for r in range(maxC)] for n in range(maxC)]
nCr[0][0] = 1
for n in range(1, maxC):
    nCr[n][0] = nCr[n][n] = 1
    for r in range(1, n):
        nCr[n][r] = (nCr[n-1][r-1] + nCr[n-1][r]) % MOD

RES = [[0 for i in range(maxC)] for j in range(maxD)]
for d in range(maxD):
    RES[d][0] = 1
for d in range(1, maxD):
    for c in range(2, maxC, 2):
        for pridame in range(0, c+1, 2):
            pocet_v_menej_dimenziach = RES[d-1][c-pridame]
            pozicie_pridanych = nCr[c][pridame]
            ochutenie_pridanych = nCr[pridame][pridame//2]
            RES[d][c] += pocet_v_menej_dimenziach * pozicie_pridanych * ochutenie_pridanych
        RES[d][c] %= MOD

for g in Gulky:
    print(RES[g[0]][g[1]])