4. Átriové problémy vzorové riešenie

5 3
20 4 5 7 3
2 2 2
1 4 3
4 2 5

0
1
1

Ak si odmyslíme príbeh, našou úlohou je načíťať \(n\) čísel a potom nájsť na nejakých úsekoch súčin týchto čísel, vždy modulo nejaké iné číslo.

Prvá vec, ktorá by programátorovi mala napadnúť v úlohe, kde sa vyskytuje nejaký typ otázok, je, čo si môžeme predpočítať pred ich samotným spracovávaním. Začnime ale na začiatok riešením hrubou silou, ktoré si nič nepotrebuje predpočítať.

Bruteforce

Na začiatku načítame čísla na vstupe. Potom postupne načítavame otázky a každú z nich hneď po načítaní zodpovieme. Pre každú otázku prejdeme zadaný úsek zľava doprava a postupne násobíme čísla v úseku, pričom si medzivýsledok priebežne modulujeme.

Takéto riešenie má časovú zložitosť na jednu otázku až \(O(n)\), keďže existujú otázky, ktoré nás donútia prejsť celé pole. Pre \(q\) otázok to teda dáva celkovú časovú zložitosť \(O(n \cdot q)\) a pamäťovú \(O(n)\), kedže si pamätáme iba čísla na vstupe.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    // optimalizacia I/O
    ios_base::sync_with_stdio(false);
    
    int n, q;
    long long odp;
    cin >> n >> q;
    
    vector<int>cisla(n);
    
    //nacitame si cisla
    for(int i=0;i<n;++i) cin >> cisla[i];
    
    int l, r, m;
    for(int f=0;f<q;++f)
    {
        cin >> l >> r >> m;
        --l;
                
        //prechadzame pole, nasobime odp a zaroven modulujeme
        odp = 1;
        for(int i=l;i<l+r;++i) odp = (odp*cisla[i]) % m; 
        
        cout << odp << "\n";
    }
    
    return 0;
}

Toto riešenie funguje v praxi veľmi dobre, ale na ozaj veľkú sadu stačiť nebude. Na vzorové riešenie sa ešte budeme musieť zamyslieť. Ako sme spomenuli, podozrivé nám môže byť, že sme si nič nepredpočítavali pred samotným spracovávaním otázok.

Prefixové súčty a prečo sú veľké čísla zlé

Ak vám pojem prefixové súčty nie je známy, pred čítaním zvyšku vzoráku sa vám oplatí sa s ním zoznámiť, napríklad v kuchárke.

Prefixové súčty riešia príbuzný problém, kde namiesto súčinu čísel v úseku chceme zistiť ich súčet. Uvedomme si ale, že tu nefunguje niečo ako “prefixové súčiny”. Nevieme si pre každé políčko \(x\), od \(1\) po \(n\), vypočítať \(k_1 \cdot k_2 \cdot ... \cdot k_x\), nakoľko takéto číslo môže byť naozaj veľké.

Čo je také zlé na veľkých číslach? A aké veľké čísla by to boli? V poradí \(i\)-ty súčin je súčinom prvých \(i\) čísel, každé z nich je od \(1\) do \(100\). Na jeho uschovanie by sme preto potrebovali až rádovo \(i \cdot \log 100\) bitov. Všetky prefixové súčiny by teda zaberali až \(O(n^2)\) pamäte, a zaplnenie tejto pamäte by trvalo až \(O(n^2)\) času. Navyše, pri implementácii v C++ by sme si museli implementovať vlastný typ pre veľké čísla a aritmetiku na ňom, nakoľko long long nestačí.

Dokonca, problém s nimi nie je len ten, že zaberajú veľa miesta. Ak by sme chceli sčítať dve čísla dĺžky \(i\), trvalo by nám to až \(O(i)\) času. A ich súčin by trval ešte dlhšie. Vidíme teda, že veľké čísla sú zlé, pretože operácie s nimi trvajú dlho.

V úlohe je veľmi dôležité, že nás zaujíma zvyšok súčinu po delením nejakým relatívne malým číslom \(m \leq 10^9\). Ak by nás zaujímal celý súčin, dostali by sme veľké číslo. Už len jeho výpis by trval dlho.

Vo zvyšku textu sa veĺkým číslam vyhneme tak, že všetky medzivýsledky budeme modulovať \(m\). Nebojte sa, vždy, keď tak učiníme, na to upozorníme. Priebežným modulovaním si zaručíme, že budeme vždy narábať s číslami do \(10^9\). Operácie s nimi teda budú zaberať konštantne veľa času.

Vzorové riešenie

Keď čítame úlohu, môžeme sa snažiť nájsť niečo, čo nám udrie do očí, akúsi slabinu úlohy. Tu si všimneme, že čísla na vstupe nie sú veľké, sú do \(100\). Toto by sme snáď mohli využiť. Ak dostaneme nejaký úsek, zjavne v ňom bude najviac \(100\) rôznych čísel. Ich počty môžu byť veľké, avšak nikdy týchto čísel nebude veľa rôznych. Predstavme si, že poznáme počty výskytov jednotlivých čísel. Teda, že pre každý úsek a každé číslo \(x\) vieme rýchlo povedať, koľkokrát sa číslo \(x\) nachádza v danom úseku. Ako vieme toto využiť? Ak máme takúto informáciu, stačí nám vynásobiť jednotlivé čísla umocnené na počty ich výskytov, pričom to berieme modulo \(m\), a dostaneme našu odpoveď. Ako rýchlo však vieme umocniť \(x\) na \(i\)-tu, modulo \(m\)?

Zrekapitulujme si to. Máme dva podproblémy, ktoré chceme vedieť riešiť. Po prvé, chceme vedieť pre ľubovoľný úsek rýchlo povedať, koľkokrát sa v ňom ktoré číslo nachádza. Po druhé, chceme vedieť rýchlo umocniť \(x\) na \(i\)-tu modulo \(m\). Začnime riešením prvého.

Ako zistiť počet výskytov jednotlivých čísiel na intervale? Predstavme si, že sa pýtame na počet výskytov čísla \(42\). Každé číslo v poli buď je \(42\) a prispeje do výsledku \(+1\), alebo nie je \(42\) a prispeje \(0\). Vytvorme si teda pomocné pole dĺžky \(n\), kde si na pozíciách, kde boli v pôvodnom poli \(42\)-ky, budeme pamätať jednotky a na ostatných pozíciách nuly. Počet \(42\)-jek v nejakom úseku v pôvodnom poli je rovný súčtu čísel v rovnakom úseku v našom pomocnom poli. A súčty čísel v úsekoch vieme rýchlo počítať pomocou prefixových súčtov.

Nás ale nezaujíma odpoveď len pre \(42\), ale pre všetky čísla od \(1\) po \(100\). Tak budeme mať \(100\) pomocných polí s prefixovými súčtami – jedno pre každé z týchto čísel. Predpočítať si ich nám zaberie \(O(100 \cdot n) = O(n)\) času. Následne vieme v konštantnom čase zistiť počet výskytov nejakého čísla v ľubovolnom úseku.

Vrhnime sa na druhý podproblém: ako sa dá rýchlo umocniť \(x\) na \(i\)-tu, modulo \(m\)?

Jedným cyklom by sme to vedeli zaiste v \(O(i)\). Avšak, čo ak je \(i\) naozaj veľké, tak ako v našom prípade? Využijeme techniku opakovaného umocňovania na druhú. Tá sa dá elegantne implementovať za pomoci rekurzie. Ak máme umocniť \(x^i\) a \(i\) je nepárne, tak si rekurzívne vypočítame \(x^{i-1}\) a vrátime túto hodnotu vynásobenú \(x\), modulo \(m\). Rozdiel oproti pomalému umocňovaniu uvidíme v prípade, keď \(i\) je párne. Vtedy si vieme rekurzívne vypočítať \(x^{\frac{i}{2}}\). Ak označíme túto hodnotu \(pom\), \(x^i\) dostaneme zadarmo ako \(pom \cdot pom\) alebo \(pom^2\), modulo \(m\).

Akú ma toto časovú zložitosť? Môžme nahliadnuť, že aspoň každý druhý krok klesne \(i\) na polovicu. Koľko krát môže takto klesnúť? Nanajvýš \(O(\log i)\)-krát, čo je aj výsledná časová zložitosť tohto rekurzívneho umocňovania. V kontexte našej úlohy je počet výskytov nejakého čísla v nejakom úseku vždy nanajvýš \(n\). Časová zložitosť bude teda \(O(\log n)\).

Aká je celková časová zložitosť nášho algoritmu? Spočítanie si prefixových súčtov nám trvá \(O(n)\). Následne, spracovanie každej z \(q\) otázok trvá \(O(100 \cdot \log{n}) = O(\log n)\). Dokopy máme časovú zložitosť \(O(n + q \cdot log(n))\). Toto riešenie si potrebuje pamätať prefixové súčty polí dĺžky \(n\), z čoho vyplýva pamäťová zložitosť \(O(n)\).

#include <iostream>
#include <vector>

using namespace std;

// funkcia, ktora umocni "x" na "n"-tu a to modulo "mod_m" v case O( log(n) )
long long umocni(long long x, long long n, long long mod_m)
{
    // vsetko na 0-tú je 1
    if(n == 0)return 1;
    
    // ak je n nepárne
    if( (n%2) == 1) return (x*umocni(x, n-1, mod_m)) % mod_m;
    
    // ----
    // sem sa dostaneme iba ak je n párne
    // ----
    
    //ak je n párne, zisti hodnotu x^(n/2) a uloz ju do pom
    long long pom = umocni(x, n/2, mod_m);
    
    return (pom*pom) % mod_m;
}

int main()
{
    // optimalizacia I/O
    ios_base::sync_with_stdio(false);
    
    long long n, q;
    cin >> n >> q;
    
    vector<long long> cisla(n);
    
    for(long long i=0;i<n;++i) cin >> cisla[i];
    
    vector<vector<long long> > prefix (n+1, vector<long long> (101, 0));
    
    for(long long i=1;i<=n;++i)
    {
        prefix[i] = prefix[i-1];
        ++prefix[i][cisla[i-1]];
    }
    
    long long l, r, m, odp;
    for(long long f=0;f<q;++f)
    {
        cin >> l >> r >> m;
        
        --l;
        r += l;
        
        odp = 1;
        for(long long i=0;i<101;++i)
        {
            if( prefix[r][i] - prefix[l][i] > 0)
            {
                odp *= umocni(i, prefix[r][i] - prefix[l][i], m);
                odp %= m;
            }
        }
        cout << odp << "\n";
    }
    
    return 0;
}