Zadanie

Vlejd vystúpil z autobusu. Prišiel práve na internáty a jediné, čo ho ako správneho študenta zaujíma je to, kde zohnať jedlo. Vonku panuje treskúca zima. On však vie, že cestou za jedlom bude musieť ešte prekonať bájny kopec ku átriovým domom1 a až tam ho čaká odmena, v podobe najlepšej jedálne v Mlynskej doline.

Po chvíli celý uzimený dôjde do jedálne a tam vidí dlhý rad stolov s jedlom. Pri prvom podávajú \(30\) rôznych rezňov, pri druhom \(50\) rôznych šalátov. Inde zas \(10\) druhov koláča a takto by mohla jeho myseľ pokračovať vééľmi dlho. Vidí prichádzať zmrznutých študentov, ktorí už nemyslia na nič iné ako na jedlo. Vtom si uvedomí, ako hlúpo sa hladní študenti správajú.

Každý študent si zoberie tácku a prechádza okolo stolov s jedlom. V jednom momente uvidí na stole, pri ktorom sa práve nachádza, druh jedla, na ktorý má chuť. Zoberie si ho a vtom sa začne správať iracionálne a pažravo. Z každého ďalšieho stolíka si vyberie nejakú vec a prihodí si ju na tácku. Takto pokračuje, pokým si neuvedomí, že už na ďalšie jedlo nemá peniaze. Vtedy skončí s prihadzovaním jedla na tácku, odkráča k pokladni a zaplatí.

Ako to už chodí, každého študenta zaujíma, z koľkých možností má na výber. Vlejd je schopný programátor a tak si povedal, že by skúsil študentom uľahčiť život. Práve prebiehajúce skúškové mu však neumožnuje sústrediť sa na nič iné ako na školu. Pomôžte mu a vyriešte túto úlohu zaňho.

Úloha

V jedálni stojí v jednom dlhom rade \(n\) stolov s jedlom. Na \(i\)-tom stole od začiatku je \(k_{i}\) rôznych druhov jedla. Každé jedlo stojí \(1\) euro.

Ak má teda nejaký študent \(x\) eur a jedlo si začne brať pri \(a\)-tom stole, vydržia mu peniaze až po stolík s číslom \(a+x-1\). Na tácke nakoniec bude mať jednu z \(k_{a} \cdot k_{a+1} \cdot ... \cdot k_{a+x-1}\) možností.

Pre každého študenta vieme, pri ktorom stole si začne brať jedlo a koľko má peňazí. Vypočítajte, z koľkých rôznych možností si môže vybrať.

Tento počet, samozrejme, môže byť veľmi veľké číslo a jednotlivým študentom nemusí dávať priveľký zmysel. Pre každého študenta teda dostanete jeho kapacitu: najväčšie číslo, ktoré si vie predstaviť. Vypíšete zvyšok výsledku po delení týmto číslom.

Formát vstupu

Na prvom riadku vstupu sú dve celé čísla \(n, q\) (\(1 \leq n, q \leq 10^{5}\)): počet stolov v jedálni a počet študentov. Na druhom riadku vstupu sa nachádza \(n\) čísel \(k_1, k_2, \dots k_n\) (\(1 \leq k_{i} \leq 100\)), kde číslo \(k_{i}\) udáva počet rôznych možností, z ktorých má študent na výber pri \(i\)-tom stole.

Na každom z ďaľších \(q\) riadkov je popis jedného študenta pozostávajúci z troch čísel \(a, x, m\) (\(1 \leq a \leq n\), \(1 \leq x\) a \(2 \leq m \leq 10^{9}\)). Tie hovoria, že študent si začne brať jedlo pri \(a\)-tom stole (stoly číslujeme od \(1\)), má pri sebe \(x\) peňazí a jeho kapacita je \(m\).

Môžete navyše predpokladať, že každému študentovi dôjdu peniaze najneskôr pri poslednom stole, teda že \(a+x-1 \leq n\).

Formát výstupu

Pre každého študenta vypíšte na samostatný riadok jedno číslo: počet možností, z ktorých má na výber, modulo jeho kapacita.

Hodnotenie

Vaše riešenie bude otestované na \(4\) sadách vstupov. Pre jednotlivé sady platia tieto obmedzenia:

číslo sady \(1\) \(2\) \(3\) \(4\)
\(n, q \leq\) \(1\,000\) \(10\,000\) \(100\,000\) \(100\,000\)

Upozorňujeme, že aj vzorové riešenie napísané v nejakom z pomalších jazykov, napr. v Pythone, nemá prakticky žiadnu šancu proti väčším vstupom.

Príklad

Input:

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

Output:

0
1
1

Prvý súčin vychádza \((4 \cdot 5) \bmod 2 = 0\), druhý \((20 \cdot 4 \cdot 5 \cdot 7) \bmod 3 = 2800 \bmod 3 = 1\) a tretí \(21 \bmod 5 = 1\).


  1. Ide o časť internátov, ktoré si obľúbite aj vy, ak budete niekedy študovať na matfyze alebo sa zúčastníte Letnej školy Trojstenu. Nachádzajú sa tam totiž všetky dobré jedálne v okolí internátov.

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

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ť.

  • Dávid Midlik

    odoslané 3. jún 2018 21:32

    môj prvý koment