Omówienie zadania Żyrandol (III etap XXXI OI)

Kilka ustaleń

Żyrandol będziemy reprezentowali jako drzewo, gdzie gniazda są wierzchołkami, a połączenia między gniazdami są krawędziami. Drzewo jest ukorzenione w wierzchołku $1$. Dla ustalonego wierzchołka $v$ jego sąsiedzi, którzy są głębiej, to jego dzieci, a wierzchołek, który jest płycej, to rodzic.

Zapytanie $i$ dotyczy części drzewa, której wierzchołki są na głębokości co najwyżej $p_i$. W tym fragmencie drzewa zastanawiamy się ile jest ścieżek prostych (wierzchołki się nie powtarzają), gdzie kolejne typy wierzchołków na ścieżce odpowiadają kolejnym wartościom ciągu $a$.

Rozwiązanie brutalne

W rozwiązaniu brutalnym możemy wygenerować dla każdego zapytania odpowiednie drzewo i z każdego wierzchołka uruchomić algorytm DFS, który zliczy ile jest ścieżek zaczynających się w danym wierzchołku zgodnych z ciągiem z zapytania.

To rozwiązanie przechodzi pierwsze podzadanie.

Struktura drzewa

Z każdym poziomem (zbiór wierzchołków o tej samej głębokości) rozmiar drzewa rośnie wykładniczo, więc musimy zrozumieć, jak zwięźle reprezentować wierzchołki na kolejnych poziomach. Po rozrysowaniu kilku poziomów drzewa możemy zauważyć, że jest ono dosyć regularne. Konkretniej, zbiór typów dzieci danego wierzchołka zależy tylko i wyłącznie od jego własnego typu. Z czego to wynika?

Przeanalizujemy proces składania żyrandola patrząc tylko na typy wierzchołków. Zakładamy, że $k \ge 1$, ponieważ przypadek $k = 1$ jest oczywisty. Ciąg typów wierzchołków to $1, 2, 3, \dots, k, 1, 2, 3, \dots, k, $ itd. Na początku musimy przydzielić dzieci wierzchołkowi typu $1$ i typ następnego wierzchołka, który możemy przydzielić, to $2$. Zastanówmy się, co się stanie po przydzieleniu dzieci do pierwszych $k$ wierzchołków. Wierzchołek typu $1$ ma $1$ dziecko, wierzchołek typu $2$ ma $2$ dzieci, itd., czyli sumarycznie $k$ wierzchołków, każdy innego typu, mają $\dfrac{k(k+1)}{2}$ dzieci. Teraz, dzięki temu, że $k$ jest nieparzyste, $k + 1$ jest parzyste, więc tych dzieci jest $k \cdot c$, gdzie $c$ jest całkowite i $c = \dfrac{k + 1}{2}$. Zatem, gdy będziemy przydzielać dzieci drugiemu wierzchołkowi typu $1$, kolejny wierzchołek, którego jeszcze nie przydzieliliśmy, będzie ponownie typu $2$. Otrzymaliśmy sytuację identyczną do początkowej, więc wierzchołki kolejnych typów też otrzymają ten sam zbiór typów dzieci.

Uproszczenie zapytań

Mamy już zwięzły opis całego drzewa, ale nie wiemy jeszcze, jak użyć go do zliczania ścieżek. Sprowadzimy takie zapytania do prostszych, w których dla każdego zapytania $i$ mamy $d_i = 1$.

W każdej zliczanej przez nas ścieżce jest dokładnie jeden wierzchołek o najmniejszej głębokości i musi on odpowiadać jakiejś pozycji w ciągu $a_i$. Powiedzmy, że jest to pozycja $r$. Teraz weźmy dowolny wierzchołek $v$ w drzewie, który ma głębokość $g$ i zastanówmy się ile jest ścieżek, w których ten wierzchołek pełni powyższą rolę.

Aby istniała przynajmniej jedna ścieżka, to na pewno musi być spełnione $g + r - 1 \leq p_i$ oraz $g + (d_i - r) \leq p_i$, ponieważ zaczynając od pozycji $r$ kolejne wierzchołki w lewo i na prawo mają rosnące o $1$ głębokości i końce ścieżki muszą mieć głębokość co najwyżej $p_i$.

Drugi warunek jest taki, że wierzchołki $r - 1$ oraz $r + 1$ na ścieżce są dziećmi $r$-tego wierzchołka, więc $a_{i, r - 1} \neq a_{i, r + 1}$, ponieważ każdy typ występuje co najwyżej raz jako dziecko wierzchołka, a na ścieżce nie mogą powtarzać się takie same wierzchołki.

Musimy jeszcze zapewnić, że $j$-ty $(1 < j \leq r)$ wierzchołek na ścieżce jest rodzicem $j - 1$-wszego wierzchołka i analogicznie $g$-ty $r \leq g < d_i$ wierzchołek jest rodzicem $g + 1$-wszego. Wystarczy nam do tego sprawdzenie, czy wierzchołek typu $a_{i, j}$ posiada jako dziecko wierzchołek typu $a_{i, j - 1}$ (analogicznie dla $g$), co wynika ze struktury drzewa.

Jeśli dla wierzchołka $v$ i przypisanemu mu $r$ oraz $g$ są spełnione wszystkie powyższe warunki, to istnieje dokładnie jedna ścieżka, którą musimy dla niego zliczyć. Jest tak dlatego, że jeśli istnieje przynajmniej jedna ścieżka (a to gwarantują nam nasze warunki), to jest ona wyznaczona jednoznacznie, ponieważ wierzchołek typu $x$ ma co najwyżej jedno dziecko typu $y$.

Dzięki typ obserwacjom trudność naszego zadania sprowadza się do szybkiego odpowiadania na pytania: Ile jest wierzchołków typu $a$ w drzewie o głębokości $p$?

Zliczanie wystąpień

Możemy jeszcze bardziej uprościć nasze zadanie. Jeśli zliczymy wierzchołki w drzewie o głębokości $p$ $-$ oznaczmy ich liczbę przez $w$ $-$ to wynikiem będzie $\lfloor w / k \rfloor + [w \mod k < a]$, gdzie $[x < y]$ jest równe $1$ jeśli $x < y$ oraz $0$ w przeciwnym wypadku. Zatem wystarczy dla danego $p$ obliczyć rozmiar drzewa o głębokości $p$.

Struktura jednego poziomu

Rozważmy jeden poziom na głębokości $g$. Idąc kolejno od najmniejszego do największego numeru, pogrupujmy wierzchołki w bloki rozmiaru $k$ i na końcu resztę rozmiaru mniejszego niż $k$. Jeden blok zawiera po jednej liczbie od $1$ do $k$, więc na następnym poziomie drzewa te wierzchołki mają razem dokładnie $\dfrac{k(k + 1)}{2}$ dzieci. Pośród tych dzieci jest $\dfrac{k + 1}{2}$ wierzchołków każdego typu. Stąd wnioskujemy, że obchodzi nas tylko jak wygląda reszta $-$ przedział (cykliczny) typów $[l, r]$ oraz liczba bloków. Przejście między dwoma poziomami zamodelujemy jako przejście między resztą $[l, r]$, a resztą $[l', r']$. Przy takim przejściu, jeśli mieliśmy na poprzednim poziomie $b$ bloków, to w następnym będziemy mieli $b \cdot k + f(l, r)$ bloków, gdzie $f(l, r)$ oznacza liczbę bloków pośród dzieci wierzchołków o typach z przedziału $[l, r]$. Możemy takim podejściem rozwiązać trzecie podzadanie, jeśli umiejętnie przygotujemy powyższe liczności dla odpowiedniego prefiksu głębokości drzewa.

Struktura reszt

Zastanówmy się ile różnych reszt $[l, r]$ jest osiągalnych z reszty $[1, 1]$. Pomińmy kilka poziomów, aby na naszym poziomie był przynajmniej jeden blok. Powiedzmy, że mamy teraz resztę $[l, r]$. Następna reszta będzie postaci $[r + 1, h(r)]$, gdzie $h(r)$ oznacza typ dziecka o największym numerze wierzchołka typu $r$. Stąd wnioskujemy, że od pewnego momentu, który następuje bardzo szybko, następna reszta jest zdeterminowana przez $r$, więc reszt będzie sumarycznie $O(k)$.

Spójrzmy na reszty jako graf. Każdej reszcie odpowiada jeden wierzchołek i z każdego wierzchołka wychodzi dokładnie jedna krawędź skierowana do wierzchołka odpowiadającego następnej reszcie. Jeśli rozważymy tylko wierzchołki osiągalne z wierzchołka startowego odpowiadającego reszcie $[1, 1]$, nasz graf będzie zawierał jeden cykl i ścieżkę wchodzącą do tego cyklu (zaczynającą się w $[1, 1]$).

Rozwiązanie wzorcowe

Weźmy dowolną głębokość $g$ (która determinuje resztę $[l, r]$) i rozważmy wektor $[b, s, 1]$, gdzie $b$ oznacza liczbę bloków na głębokości $g$, a $s$ sumaryczną liczbę bloków w drzewie głębokości $g$. Powyższe przejście do następnego poziomu możemy zamodelować jak przemnożenie przez macierz rozmiaru $3 \times 3$, która daje następujące przejście: $$[b, s, 1] \rightarrow [b \cdot \dfrac{k + 1}{2} + f(l, r), s + b \cdot \dfrac{k + 1}{2} + f(l, r), 1]$$

Możemy na krawędzi umieścić macierz odpowiadającą opisanemu przejściu i naszym zadaniem jest przejść $p$ krawędziami i wymnożyć wektor początkowy $[0, 0, 1]$ przez macierze na kolejnych krawędziach. Niestety jeszcze nie jest to wystarczająco szybkie.

Skorzystamy teraz ze struktury grafu reszt - tworzy tak zwaną meduzę, ale interesują nas tylko ścieżki zaczynające się od wierzchołka reprezentującego $[1, 1]$, więc możemy po prostu uznać, że graf ma kształt $\rho$. Będziemy też korzystać z własności mnożenia macierzy - łączności. W ogólności, ścieżka, którą byśmy przeszli w powyższym rozwiązaniu, możemy opisać jako fragment ścieżki wchodzącej do (jedynego) cyklu w tym grafie, ileś okrążeń całego cyklu i na koniec jeszcze jakiś fragment cyklu. Możemy przeliczyć iloczyn macierzy na każdym prefiksie ścieżki i cyklu zaczynając od wierzchołka na cyklu, do którego wchodzi ścieżka. Dodatkowo znamy iloczyn wszystkich macierzy na cyklu (zaczynając od tego samego wierzchołka). Część odpowiadającą za fragment ścieżki wchodzącą do cyklu i odpowiedni fragment cyklu już mamy obliczoną, a część odpowiadającą za okrążenie całego cyklu jakąś całkowitą liczbę razy to wzięcie do odpowiedniej potęgi macierzy odpowiadającej całemu cyklowi. W ten sposób uzyskujemy rozwiązanie działające w złożoności $O(k + S \log p)$.

Bonusowe usprawnienie

Możemy jeszcze trochę przyspieszyć nasze rozwiązanie wykorzystując fakt, że za każdym razem potęgujemy tą samą macierz $M$. Obliczymy najpierw $M^1, M^2, ..., M^c$ oraz $M^c, M^{2c}, ..., M^{c^2}$, gdzie $c = \sqrt{10^9} + 1$. Korzystając z tych macierzy możemy obliczyć $M^x$ zapisując je jako $M^{yc + z}$, gdzie $y, z \leq c$. Otrzymujemy w ten sposób złożoność $O(k + S + \sqrt{p})$, ale nie jest to konieczne do uzyskania kompletu punktów.