Star Trek

Gra jest dwuosobowa przeprowadzona na wyżej zdefiniowanym drzewie $T$, gdzie wierzchołek jest zadany jako para $(i,v)$ oznaczająca, że wierzchołek znajduje się w $i$-tym drzewie $(0\le i\le D)$ w wierzchołku $G$ o numerze $v$ $(1\le v\le n)$. W jednym ruchu gracz może przesunąć pionek wzdłuż krawędzi, ale nie może wrócić do takiej pary $(i,v)$, która była już odwiedzona. Gracze grają na przemian i przegrywa ten gracz, który nie może już wykonać ruchu. Należy założyć, że gracze grają optymalnie.

Liczbę takich pasujących par wierzchołków (nazwanymi dodatkowymi krawędziami) $$(A_0,B_0),(A_1,B_1),\dots ,(A_{D-1},B_{D-1})$$ należy wypisać modulo ${10}^9+7$.

Podzadanie 2

Jeżeli $n=2$, to gracz zaczynający grę zawsze może wygrać. Przykładową jego strategią może być zawsze używanie krawędzi z $G$. Wtedy drugi gracz zawsze musi przejść przez dodatkową krawędź, chyba że taka już nie istnieje (i wtedy drugi gracz przegrywa). Istnieje więc $4^D$ sposobów na dodanie dodatkowych krawędzi. Liczbę $4^{D}mod({10}^9+7)$ można policzyć szybkim potęgowaniem w czasie $O(\log D)$.

Gra dla dowolnego drzewa

Mając dane dowolne drzewo zakorzenione w pewnym wierzchołku, w czasie liniowym można policzyć dla każdego wierzchołka (na przykład DFS-em) informację, czy wygra gracz zaczynający z pionkiem w tym wierzchołku przy dodatkowym założeniu, że pionek nie może przejść do ojca tego wierzchołka (czyli można się poruszać tylko w poddrzewie tego wierzchołka), w następujący sposób:

• Jeżeli ten wierzchołek jest liściem, to gracz zaczynający w tym wierzchołku jest w stanie przegrywającym, ponieważ nie może wykonać żadnego ruchu.
• Jeżeli wierzchołek nie jest liściem oraz istnieje syn, który jest stanem przegrywającym, to ten wierzchołek jest w stanie wygrywającym, ponieważ można przesunąć pionek w kierunku tego syna.
• Jeżeli wierzchołek nie jest liściem oraz każdy jego syn jest stanem wygrywającym, to ten wierzchołek jest w stanie przegrywającym, ponieważ nieważne jaki ruch się wykona, przeciwny gracz będzie w stanie wygrywającym, więc potrafi pociągnąć grę do jego wygranej.

Można dzięki temu algorytmowi w czasie $O(n)$ sprawdzić, czy gracz zaczynający z pionkiem w danym wierzchołku $r$ wygra grę przy założeniu, że gracze grają optymalnie.

Podzadanie 3

Przy ograniczeniach $n\le 100,D=1$ wystarczy wypróbować każdą możliwą dodatkową krawędź i powyższym algorytmem sprawdzić, czy gracz zaczynający grę ma stan wygrywający.

Krytyczne stany przegrywające

Zamiast wyliczać całe drzewo powstałe przez $D+1$ kopii drzewa $G$, lepiej jest się skupić na spreprocessowaniu odpowiednich informacji drzewa $G$, które będzie można „łączyć” pomiędzy kolejne kopie drzewa $G$.

Dla danych dodatkowych krawędzi $(A_0,B_0),(A_1,B_1),\dots ,(A_{D-1},B_{D-1})$, jeżeli wiadomo, czy wierzchołek $(1,B_0)$ drzewa $T$ jest wygrywający, czy przegrywający, można policzyć w jaki sposób dodanie dodatkowej krawędzi $(A_0,B_0)$ wpłynie na stany wierzchołków $(0,v)$ dla $v\in G$.

Ogólniej można to sobie wyobrażać jako dodanie do pewnego wierzchołka $v$ zakorzenionego drzewa $G$ w wierzchołku $r$ nowego syna $u$ o pewnym stanie (przegrywającym lub wygrywającym) i wyliczenie nowego stanu korzenia drzewa $G$. Taki proces będzie wykonywany łącznie $D$ razy.

Z definicji stanów w algorytmie gry dla dowolnego drzewa wynika, że stan wierzchołka $v$ zmieni się tylko wtedy, gdy $v$ oraz $u$ są stanami przegrywającymi (i wtedy $v$ stanie się stanem wygrywającym). Wtedy ojciec wierzchołka $v$ (oznaczany jako $parent(v)$) zmieni swój stan tylko wtedy, gdy $parent(v)$ jest stanem wygrywającym. Analogicznie można rozpatrywać kolejne przodki wierzchołka $v$. W takim razie, jeżeli stany wierzchołków $v,parent(v),parent(parent(v)),...,r$ są na zmianę przegrywające, wygrywające, przegrywające, ..., to podczepienie $u$ do wierzchołka $v$ sprawi, że korzeń zmieni swój stan, o ile $u$ jest stanem przegrywającym (i wtedy $v$ będzie nazywany krytycznym stanem przegrywającym dla korzenia $r$). Niech zbiór wszystkich takich $v$, których łańcuszek stanów do korzenia jest takiej postaci, będzie oznaczony jako $C_r$. Da się ten zbiór wyznaczyć dla konkretnego $r$ w czasie $O(n)$.

Podzadanie 4

Zadanie przy ograniczeniach $n\le 1000,D=1$ można rozwiązać w następujący sposób.

Niech $W$ -- zbiór wierzchołków $G$, dla których rozpoczęcie gry z pionkiem w tym wierzchołku jest stanem wygrywającym, oraz $L$ -- zbiór wierzchołków $G$, dla których rozpoczęcie gry z pionkiem w tym wierzchołku jest stanem przegrywającym. Te zbiory można wyznaczyć w złożoności $O(n^2)$.

Niech drzewo o numerze $0$ będzie $G_0$ (ukorzenione w wierzchołku $1$), a drzewo o numerze $1$ będzie $G_1$ (można dowolnie wybrać korzeń). Nadal zachodzi $G_0=G_1=G$, ale zostały odróżnione dla zwięzłości oznaczeń.

Jeżeli korzeń $G_0$ jest w stanie wygrywającym, to po dodaniu dodatkowej krawędzi zmieni swój stan tylko wtedy, gdy do wierzchołka z $C_1$ zostanie doczepiony jakiś korzeń $G_1$, który jest w stanie przegrywającym. Dlatego wynik (liczba sposobów dodania dodatkowej krawędzi, aby korzeń $T$ był w stanie wygrywającym) wynosi $n|W|+(n-|C_1|)|L|$ (korzenie wygrywające $G_1$ można doczepić gdziekolwiek, a przegrywające tylko do wierzchołków spoza $C_1$).

Jeżeli korzeń $G_0$ jest w stanie przegrywającym, to tylko doczepienie korzenia przegrywającego $G_1$ do wierzchołka $C_1$ sprawi, że korzeń $G_0$ zmieni swój stan na wygrywający, dlatego wynik wynosi $|C_1|\cdot |L|$.

Podzadanie 5

Dla $D=1$ można zastosować podejście z podzadania 4, ale należy przyśpieszyć rozwiązanie, czyli szybciej wyznaczyć zbiory $W$ oraz $L$ (nie trzeba przyśpieszyć wyznaczania $C_1$, ponieważ jest wyznaczany w czasie liniowym).

Można to zrobić techniką nazywaną przekorzenieniem drzewa. Należy zacząć od użycia algorytmu z gry dla dowolnego drzewa i policzyć wynik dla każdego poddrzewa przy założeniu, że korzeniem jest $r=1$, a następnie DFS-em zmieniać korzeń na każdy inny wierzchołek. W momencie, gdy jest zmieniany korzeń z $r_1$ na $r_2$ (gdzie $r_2$ jest sąsiadem $r_1$), to mogą się zmienić tylko dwa stany poddrzew (tylko wierzchołków $r_1$ oraz $r_2$), ponieważ reszta poddrzew nie zmieni swojego zbioru wierzchołków. Wystarczy więc przy przekorzenieniu ponownie obliczyć stany gry dla dwóch wierzchołków (a przy wyjściu z DFS-a cofnąć te zmiany). Otrzymujemy dzięki temu wyznaczanie zbiorów $W$ oraz $L$ w czasie $O(n)$, co rozwiązuje to podzadanie także w czasie $O(n)$.

Podzadanie 6

Przy $n\le 1000,D\le {10}^5$, można policzyć następującą wartość.

Niech $L_D$ oznacza liczbę sposobów wybrania wierzchołka początkowego oraz wybrania dodatkowych krawędzi, aby gracz zaczynający przegrał, przy założeniu, że jest $D+1$ identycznych drzew i można zacząć z dowolnego wierzchołka.

Wiadomo już, że na $|C_v|\cdot L_{D-1}$ sposobów można zmienić stan wybranego wierzchołka początkowego $v$ (ponieważ wystarczy dodać krawędź ze stanu przegrywającego do wierzchołka ze stanem krytycznym). Aby $v$ stał się stanem wygrywającym, należy albo zmienić jego stan, albo nie zmienić, w zależności od tego, jaki jest stan $v$ przed dodaniem dodatkowej krawędzi. Dlatego liczba sposobów $L_{D,v}$, aby wierzchołek początkowy $v$ był przegrywający, wynosi $|C_v|\cdot L_{D-1}$ gdy $v\in W$ oraz $n^{2D}-|C_v|\cdot L_{D-1}$ gdy $v\in L$, przy czym $L_0=|L|$.

Mamy więc $$L_D=\sum _v{L}_{D,v}=\sum _{v\in W}|C_v|\cdot L_{D-1}+\sum _{v\in L}(n^{2D}-|C_v|\cdot L_{D-1})=|L|n^{2D}+(\sum _{v\in W}|C_v|-\sum _{v\in L}|C_v|)L_{D-1},$$ gdzie $|L|n^{2D}$ oraz $(\sum _{v\in W}|C_v|-\sum _{v\in L}|C_v|)$ można spreprocessować w $O(n+\log D)$.

Szukana liczba w zadaniu wynosi $N^{2D}-L_{D,1}$ (pionek jest początkowo położony w wierzchołku $1$ drzewa $0$).

Mając wyznaczone w $O(n^2)$ liczby $|W|,|L|,\sum _{v\in W}|C_v|$ można wyznaczyć $L_D$ w czasie $O(D)$ podanym wzorem. Otrzymujemy więc rozwiązanie o złożoności czasowej $O(n^2+D)$.

Podzadanie 7

Gdy $D\le {10}^5$ oraz nie ma dodatkowego ograniczenia na $n$, można zastosować powyższe rozwiązanie, ale przyśpieszając wyznaczanie liczności zbiorów $C_v$ za pomocą przekorzenienia, tak jak w podzadaniu 5.

Podzadanie 8

Gdy nie ma dodatkowych ograniczeń, w porównaniu do poprzedniego zadania, należy szybciej wyznaczyć liczbę $L_{D,1}$.

Znając wartość $L_a$ oraz $L_b$, można wyznaczyć wzór na wartość $L_{a+b}$. Dzięki temu można skorzystać z techniki analogicznej do szybkiego potęgowania do obliczenia $L_D$, czyli na przykład poprzez wyznaczenie liczb $L_1,L_2,L_4,L_8,\dots$ i domnażając te potęgi, których bity są zapalone w $D$.

Alternatywnie, swoim ulubionym sposobem można wyprowadzić wzór na postać jawną rekurencji liniowej $L_D$, otrzymując wzór $L_{D-1}=|L|\frac{n^{2D}-E^D}{n^2-E}$ dla $E=(\sum _{v\in W}|C_v|-\sum _{v\in L}|C_v|)$, co można wyliczyć szybkim potęgowaniem oraz odwrotnością modulo.