Bol raz jeden algoritmus, ktorého každodennou prácou bolo hľadanie najdlhšej cesty v strome s vrcholmi od \(1\) po \(n\). Jeho metóda bola nasledovná:
Strom si zakoreníme za vrchol s najmenším číslom.
Pre každého syna koreňa nájdeme najdlhšiu cestu, ktorej jeden koniec je samotný syn, a druhý koniec je v jeho podstrome. To spravíme obyčajným prehľadávaním do šírky.
Vyberieme dvoch synov s najdlhšími cestami. Keď tieto dve cesty prepojíme cez koreň, dostaneme najdlhšiu cestu prechádzajúcu koreňom.
Ešte sme ale nebrali do úvahy cesty, ktoré koreňom vôbec neprechádzajú. Každá taká cesta ale leží celá v podstrome niektorého syna. Stačí preto rekurzívne vyriešiť tieto podstromy – zakoreníme ich, spočítame pre synov koreňa najdlhšie cesty, …
Kolega programátor mu poradil, že ak by za koreň vždy zvolil centroid1 (pod)stromu, tak by mal oveľa viac voľného času, lebo by vraj bežal v čase \(O(n \log {n})\) namiesto \(O(n^2)\).
Algoritmus sa nad tým zamyslel, a všimol si, že jeden strom môže mať viac ako jeden centroid. V takých prípadoch by sa musel rozhodnúť, ktorý z centroidov vybrať. S tým sa mu ale nechce otravovať. Zaujíma ho preto, koľko stromov s \(n\) vrcholmi je takých, že práca na ňom podľa nového postupu bude čisto manuálna, a nebude musieť počas nej robiť žiadne rozhodnutia.
Úloha
Strom je ľahký, ak má práve jeden centroid, a jeho odobratím sa strom rozpadne na niekoľko ľahkých stromov. Pre zadaný počet vrcholov \(n\) zistite, koľko rôznych stromov s \(n\) vrcholmi je ľahkých. (Dva stromy považujeme za rôzne, ak existujú vrcholy \(u, v\), ktoré sú hranou spojené v prvom strome, ale nie v druhom.) Toto číslo môže byť veľké, vypíšte preto jeho zvyšok po delení prvočíslom \(p\).
Formát vstupu
Na jedinom riadku vstupu sú dve celé čísla \(n, p\) oddelené medzerou. \(n\) udáva počet vrcholov a \(p\) je prvočíslo, po delení ktorým berieme zvyšok.
Je päť testovacích sád. Vo všetkých platí \(1 \leq n \leq 3\,000\), a \(n < p \leq 10^9\). Pre jednotlivé sady máme nasledovné obmedzenia:
číslo sady | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
---|---|---|---|---|---|
\(n \leq\) | \(9\) | \(100\) | \(500\) | \(1\,000\) | \(3\,000\) |
Formát výstupu
Na jediný riadok výstupu vypíšte jedno celé číslo z \(\lbrace 0, 1, \ldots, p - 1 \rbrace\) – počet vyhovujúcich stromov s \(n\) vrcholmi, modulo \(p\).
Príklady
Input:
2 103
Output:
0
Pre \(n = 2\) existuje iba jeden strom:
Tento strom nevyhovuje, nakoľko v prvom kroku môžeme za koreň zvoliť aj vrchol \(1\), aj \(2\).
Input:
4 103
Output:
4
Pre \(n = 4\) máme tieto štyri vyhovujúce stromy:
Príklad nevyhovujúceho stromu je
nakoľko môžeme v prvom kroku zvoliť za koreň \(2\) aj \(3\).
taký vrchol v strome, ktorého každý syn má podstrom obsahujúci nanajvýš polovicu všetkých vrcholov↩
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.