Zadanie

Okäň “Bzučiak” Hruškový, zákerný zločinec známy celou galaxiou, už má vyhliadnutý blištivý cieľ svojej najnovšej lúpeže. Kdesi v bode v nekonečne sa totiž nachádza legendárna planéta menom Al-Jabr, na ktorej sídli mocný panteón známy ako Okruh Celých Čísel. Bzučiak plánuje stať sa lupičom lupičov, spáchať krádež krádeží - ukradne identitu identity. Teda, povedané ako človek, ukradne identitu čísla Jeden. Na to sa vláme na prestížny diskrétny banket, ktorý Jednotka pravidelne organizuje…

Na diskrétny banket Jednotka okrem seba pozve ešte aj nejakú konečnú množinu kladných 1 celých čísel. Vrátnik dostane krásne očíslovaný zoznam, na ktorom sú všetky tieto čísla vypísané v rastúcom poradí 2. Vyzerá to napríklad takto: 1. \(2\) 2. \(3\) 3. \(7\) 4. \(9\) 5. \(10\) 6. \(12\) 7. \(13\)

Môžete si všimnúť, že to je mierne mätúci formát. A vrátnik s ním má problém tiež! Podľa protokolu by sa malo prichádzajúce číslo preukázať dokladom totožnosti, na čo vrátnik skontroluje, či je na zozname, a ak áno, dá mu menovku s jeho menom a vpustí ho na banket. Avšak vrátnik tomuto protokolu zle porozumel, a na menovku dá namiesto jeho názvu jeho poradové číslo na zozname. Teda ak by za vrátnikom so zoznamom vyššie prišlo číslo \(10\), dostane menovku s číslom \(5\), pretože je v zozname piate.

Bzučiakov plán je veľmi jednoduchý, podľa nasledovného krásne očíslovaného zoznamu: 1. Vyhliadnuť si vhodné celé ciele ☑ 1. Ukradnúť identitu niektorého z nich ☐ 2. Podstrčiť vrátnikovi vhodný falošný zoznam hostí ☐ 3. Vstúpiť na banket so svojou novoukradnutou identitou ☐ 4. Dostať menovku (vďaka chybe v systéme s nižším číslom) ☐ 5. Vstúpiť znovu na banket, preukázajúc sa novozískanou menovkou ☐ 6. Opakovať kroky \(4-5\) kým sa bude dať ☐ 7. Získať menovku s číslom \(1\) ☐ 8. Ujsť na Vesmírne Belize ☐ 9. Zo všetkých zločincov, ktorí sa kedy v galaxií činili, byť \(1\) ☐ 10. Kúpiť si zvlhčovač vzduchu ☐

Prvý krok už splnil - má zoznam čísel, ktorých identitu je schopný odcudziť. Teraz potrebuje vašu pomoc 3, aby sa rozhodol, ktorú z počiatočných identít sa mu oplatí ukradnúť najviac. Musí totiž myslieť aj na nasledujúci krok, a podstrčiť vyhovujúci zoznam hostí. Naviac je tu ešte problém s tým, že niektoré čísla vyzerajú veľmi ikonicky a ani Bzučiak, majster prestrojenia, nemusí byť schopný ich výzor napodobniť… Pre každú možnosť počiatočnej identity Bzučiakovi povedzte, koľko existuje zoznamov spĺňajúcich tieto (krásne očíslované) podmienky: 1. Aby to nebolo podozrivé, Bzučiakova pôvodná identita musí byť najvyšším (posledným) číslom v zozname. 2. Opakovaným nahrádzaním čísla jeho poradím v zozname sa po konečnom počte krokov dostaneme na číslo \(1\). 3. Ani jedno z čísel navštívených takýmto skákaním nepatrí medzi tzv. bezpečné čísla, ktoré sú zadané na vstupe.

Úloha

Na vstupe je zadaných niekoľko bezpečných čísel a niekoľko počiatočných čísel. Pre každé počiatočné číslo \(a\) vypíšte počet rôznych podmnožín \(Z\) množiny \({2,3...a}\) takých, že vzostupným zoradením a očíslovaním (od \(1\)) prvkov \(Z\) sa opakovaným nahrádzaním čísla (počnúc od \(a\)) jeho poradovým číslom dostaneme k číslu \(1\) bez toho, aby sme prešli bezpečným číslom, alebo číslom, ktoré nie je v \(Z\).

Keďže počty možností môžu byť fakt veľké, vypíšte iba ich zvyšok po delení číslom \(10^9 + 7\)

Formát vstupu

V prvom riadku vstupu sú medzerou oddelené dve čísla \(r\) a \(k\) (\(0 \leq r \leq 10^5\), \(1 \leq k \leq 10^5\)) - počet bezpečných čísel a počet počiatočných čísel.

Na nasledujúcich \(r\) riadkoch je na každom jedno celé číslo \(x_i\) - toto sú bezpečné čísla. Môžete predpokladať, že sú zoradené od najmenšieho, a žiadne dve sa nerovnajú.

Na \(k\) zvyšných riadkoch je po jednom celom čísle \(a_i\) - všetky počiatočné čísla. To isté počiatočné číslo sa môže vyskytnúť aj viackrát.

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4
\(1 \leq r,k \leq\) \(10^5\) \(10^5\) \(10^5\) \(10^5\)
\(2 \leq x_i,a_i \leq\) \(42\) \(10\) \(50\) \(200\)

V sade 1 dokonca platí, že bezpečné nie sú žiadne čísla, teda \(r = 0\).

Formát výstupu

Pre každé z \(k\) počiatočných čísel vypíšte jeden riadok s jediným číslom - počtom vyhovujúcich zoznamov pre dané počiatočné číslo.

Príklady

Input:

0 3
2
5
10

Output:

1
5
77

Pre 2 je odpoveď zrejmá - existuje len jedna prípustná množina, a 2 je v nej najnižším číslom. 5 vyhovujú nasledovné množiny: {2,3,4,5}, {2,3,5}, {2,5}, {3,4,5} a {5}.

Input:

2 3
2
4
2
5
10

Output:

0
2
23

Keďže 2 je bezpečným číslom, začať plán ním by okamžite zlyhalo. 5 vyhovujú tie množiny ako v minulom prípade, ale nesmie v nich byť navštívené 2 ani 4 (môžu byť v zozname, len im nesmieme vziať identitu): {3,4,5} a {5}.


  1. Nula je všadeprítomná a netreba ju nikam pozývať, no a záporné čísla… Povedzme, že ich prítomnosť nie je veľmi pozitívna…↩︎

  2. Samozrejme, čísla rastú na sile, čím bližšie k Nule sú, preto je zoznam vlastne zoradený podľa klesajúcej dôležitosti hostí.↩︎

  3. Áno, budete akomplicom. Nemáte však na výber, pokiaľ nebudete súhlasiť, Bzučiak na galaktický internet vypustí fotky vašeho prvého programu a vaša reputácia bude zdevastovaná.↩︎

Zadrátované riešenie

Najprv sa pozrime na veličiny, ktoré v úlohe vystupujú. Všimnime si, že otázok je síce veľa, ale čísla v nich budú pomerne malé. Vyzerá to teda, že optimálne bude výsledky pre čísla počítať dopredu, respektíve ich vypočítať, keď ich potrebujeme, a odvtedy si ich už pamätať. Možných otázok je totiž pomerne málo… V prvej sade dokonca platí, že žiadne čísla nie sú zakázané - teda v tejto sade bude odpoveď na dané číslo zakaždým rovnaká. Prvú sadu teda vieme jednoducho zriešiť tak, že najprv si nejakým ľubovoľne pomalým riešením vygenerujeme odpovede pre prvých \(42\) čísel, a potom len napíšeme program, ktorý podľa čísla na vstupe zvolí správnu odpoveď. Problémom bude, keď sa v neskorších sadách objavia aj zakázané čísla. Vtedy totiž taká istá otázka môže mať rôzne odpovede, v závislosti od toho, ktoré čísla sú zakázané… Časová zložitosť je \(O(1)\), a pamäťová zložitosť je \(O(a)\).

Bruteforce

Mohli by sme pre každé číslo na vstupe vygenerovať všetky možné podpostupnosti \(2,3,4...a\) a pre každú otestovať, či spĺňa všetky zadané podmienky. Týchto podpostupností je rádovo \(2^a\). Každú z nich musíme otestovať - ako to spraviť pomerne rýchlo? Najprv overíme, či naozaj skákaním z posledného čísla skončíme na \(1\). To vieme overiť jediným prechodom - prejdeme postupnosť od konca, a vždy, keď narazíme na číslo, na ktorom teraz sme, pozrieme sa na jeho index a ten si odteraz pamätáme. Pokiaľ pred dorazením na \(1\) nenájdeme v zozname nejaké číslo, ktoré sme dostali, vieme, že postupnosť nevyhovuje. Popri tom ešte musíme kontrolovať, či neprechádzame cez zakázané číslo. Prvotný nápad je zakaždým prezrieť celý zoznam zakázaných čísel, či sa v ňom to naše nenachádza. Stačí nám ale použiť techniku dvoch bežcov: keďže zakázaný zoznam je zoradený, a čísla, ktorých prítomnosť v ňom kontrolujeme, sa vždy znižujú, stačí nám pamätať si pozíciu medzi zakázanými číslami, teda “medzeru”, do ktorej by momentálne číslo patrilo. Na začiatku bude na konci, a posunieme ju bližšie k začiatku vždy, keď kontrolujeme číslo, ktoré je pod spodným okrajom tejto medzery. Takto toto miesto posúvame iba na začiatok, a teda počas celého kontrolovania postupnosti prejdeme jeho \(r\) prvkov najviac raz. Teda okontrolovať postupnosť má zložitosť \(O(r+a)\). V každej z \(k\) otázok ale testujeme \(2^a\) postupností, teda celková zložitosť algoritmu je \(O(k*2^a*(r+a))\). Pamäťová zložitosť je \(O(r + a)\), lebo si pamätáme postupnosť dĺžky až \(a-1\), a \(r\) zakázaných čísel.

Optimálne riešenie

Pomôže nám dynamické programovanie. Budeme si pamätať pre všetky dvojice \(a,n\) počet postupností končiacich na \(a\), ktoré majú práve \(n\) prvkov (\(n >= 2\)). Zakaždým, keď príde otázka, sčítame počty pre dané \(a\) pre všetky možné dĺžky \(n\), ak ich už poznáme. Ak ešte nie, postupne budeme počítať tieto hodnoty pre najnižšie nevypočítané \(a\), až kým sa k otázke nedostaneme.

Dobre teda, ale ako vypočítame odpoveď pre dvojicu \(a,n\)? Využijeme pri tom, samozrejme, odpovede pre nižšie \(a\). Majme teda postupnosť končiacu na \(a\) dĺžky $n%. Hneď vieme, aký bude prvý krok pri skákaní po tejto postupnosti. Keďže \(a\) je na pozícií \(n\), skočíme na číslo \(n\). Na akej pozícií môže byť toto \(n\)? Na akejkoľvek od \(1\) po \(n-1\). Prejdime všetkými a pre každú vypočítajme, koľko takých postupností existuje. Označme pozíciu, na ktorej je \(n\), ako \(s\). Uvedomme si, že prvých \(s\) čísel, až po číslo \(n\), bude tiež vyhovujúcou postupnosťou (začneme na jej konci a doskáčeme na jednotku). Teda takýchto postupností je už vypočítané množstvo - dvojica \(n,s\). Ale čo pozície po tej \(s\)-tej? Po žiadnom z jej čísel nikdy nebudeme skákať, teda môžu to byť úplne ľubovoľné čísla medzi \(n\) a \(a\). Teda predpočítanú dvojicu \(n,s\) vynásobíme kombinačným číslom \(a-n-1\) nad \(n-s-1\). Kombinačné čísla si tiež predpočítame - zakaždým, keď potrebujeme nové, sčítavame tie pred ním, využívajúc vzťah \((a-1 nad b) + (a-1 nad b-1) = (a nad b)\).

Ešte jeden detail nám chýba - zakázané čísla. Jednoducho, vždy keď počítame počet postupností pre dvojicu \(a,n\), tak ak náhodou \(a\) je zakázané, namiesto počítania hneď vrátime nulu. Na rozdiel od minulého riešenia, tentokrát sa čísla, na ktorých zakázanie sa pýtame, zvyšujú, tak použijeme rovnakú techniku, ako minule, len sa poľom zakázaných čísel hýbeme od začiatku po koniec.

Aká je teda zložitosť tohto riešenia? Potrebujeme najviac raz prejsť pole zakázaných čísel, teda \(O(r)\). Musíme vypočítať odpovede pre všetky dvojice posledného čísla a dĺžky postupnosti, čo je \(O(a^2)\) - pretože pre každú dvojicu stačí vynásobiť premennú kombinačným číslom v konštantnom čase. No a samozrejme, predpočítavame kombinačné čísla. Teda musíme vypočítať všetky kombinačné čísla až po \((a nad ?)\), a tých je \(O(a^2)\). Teda celková časová zložitosť je \(O(a^2 + r)\). Pamäťová zložitosť je tiež \(O(a^2 + r)\), pretože toľko výsledkov si predpočítavame, a k tomu máme pole zakázaných čísel.

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