Sieć światłowodowa

Tym razem omówimy zadanie Fiber-optic Network, które pojawiło się na zeszłorocznych zawodach ACM-ICPC Asia Mudanjiang Regional Contest.

| f v2 1 — Dla $| f v 1 2$ liczby w pozostałych trzech wierzchołkach możemy wybrać dowolnie, co daje 6 przyporządkowań $|2~3,1,7,4~5~6 .$ Dla $| f v 2 2$ mamy jedno przyporządkowanie $| 3,2,7,5 ,$ a dla $| f v2 3$ dwa $| 2,3,7,4~5 .$ Odpowiedzi dla kolejnych wierzchołków to 22, 14, 63 i 44.

W zadaniu tym mamy dane drzewo o $n$ wierzchołkach, a dla każdego wierzchołka $|v$ zadane liczby naturalne $1 ⩽L ⩽ R ⩽M v v$ (ograniczenia to $⩽50000n⩽ 50,M$ ). Dobrym przyporządkowaniem będziemy nazywać przyporządkowanie każdemu wierzchołkowi $|v$ liczby całkowitej z odpowiadającego mu przedziału $|[Lv,Rv]$ w taki sposób, aby liczby przyporządkowane wierzchołkom połączonym krawędzią były względnie pierwsze. Dla przejrzystości oznaczmy, że dla danego przyporządkowania $f$ liczba przypisana wierzchołkowi $v$ to $f(v).$ W zadaniu proszą nas, aby dla każdego wierzchołka obliczyć sumę liczb przyporządkowanych mu we wszystkich dobrych przyporządkowaniach. Wyniki należy podać modulo $9 |10 + 7,$ zatem wszystkie działania będziemy wykonywać modulo ta liczba.

Chwila myślenia i odrobina algorytmicznego rozsądku doprowadzają nas do wniosku, że w zadaniu nie ma na tyle "regularności" (cokolwiek by to znaczyło), aby dało się rozwiązać je inaczej niż poprzez wyznaczenie dla każdego wierzchołka $v$ oraz każdej możliwej wartości $|k,$ dla ilu dobrych przyporządkowań zachodzi $f(v) = k.$ To właśnie będzie naszym celem.

Jak można się spodziewać, zapewne sporo nam pomoże, jeżeli najpierw ukorzenimy nasze drzewo (w dowolnym wierzchołku). Rozwiązanie będzie bazowało na programowaniu dynamicznym. Oznaczymy przez $Tv$ poddrzewo ukorzenione w wierzchołku $|v,$ a przez $dp[v][k]$ liczbę dobrych przyporządkowań, dla których zachodzi $f (v) = k,$ gdy ograniczymy się jedynie do wierzchołków z poddrzewa $Tv.$ Niewątpliwie dla $v$ będących liśćmi zachodzi $dp[v][k] = 1,$ gdy $|Lv⩽ k ⩽ Rv,$ i $|dp[v][k] = 0$ dla pozostałych wartości $|k.$ Załóżmy teraz, że chcemy wyznaczyć odpowiedź dla wierzchołka $v,$ który ma $s$ synów $u1,...,us$ i mamy już wyznaczone tablice $|dp[u ],...,dp[u ]. 1 s$ Liczba dobrych przyporządkowań dla poddrzewa $Tv$ spełniających $| f(v) = k$ to iloczyn liczb dobrych przyporządkowań dla poddrzew $Tui,$ dla których $|nwd(f (ui),k) = 1.$ Zatem jeśli wprowadzimy oznaczenie

P[u][k] = Q dp[u][j ] nwd k, j 1

(zauważmy, że tak zapisana suma jest dobrze określona, gdyż tylko skończona liczba składników jest niezerowa), to dostaniemy wzór

dp[v][k] = P [u1][k] ⋅...⋅P[us][k].

(1)

Moglibyśmy po prostu przeiterować po wszystkich możliwych wartościach $k$ przyporządkowanych każdemu wierzchołkowi $u , i$ ale wtedy otrzymalibyśmy rozwiązanie co najmniej kwadratowe w zależności od $, M$ co byłoby zdecydowanie zbyt wolne. Dlatego stajemy przed kluczowym problemem szybkiego wyznaczenia $P [u][k]$ dla ustalonego syna $u.$ Skoro mowa o względnej pierwszości, to z pewnością warto poznać zbiór (różnych) dzielników pierwszych liczby $k;$ niech będą to liczby $|p1,...,pm .$ Liczby względnie pierwsze z $k$ to wszystkie liczby poza tymi, które są podzielne przez którąkolwiek z liczb $p1,...,pm .$ Dla $m$ mamy $|P[u][k] = P dp[u][j ] − P dp[u][j ], j p1S j$ co umożliwia szybkie obliczenie żądanej wartości, o ile znalibyśmy wcześniej $Pp1S jdp[u][j ].$ Życie nie jest jednak takie proste i w ogólnym przypadku nie możemy po prostu odjąć $PpiS jdp[u][ j]$ dla $|i = 1,...,m,$ gdyż wiele ze składników postaci $|dp[u][ j]$ odjęlibyśmy więcej niż raz (konkretnie tyle razy, ile $j$ ma dzielników wśród liczb $p1,...,pm$ ).

Jeśli wprowadzimy oznaczenia $w(A)$ oraz $A$ na zbiór liczb podzielnych przez liczbę $|l,$ to dostaniemy zależność

P[u][k] = Q dp[u][j ] − w(Ap1 j

(2)

Na ratunek w obliczeniu (2) przychodzi nam zasada włączeń i wyłączeń, a właściwie jej minimalne uogólnienie:

w(Ap1

Pomimo przerażającego wyglądu wzór ten jest całkiem prosty, ale jeżeli ktoś nie spotkał się z nim wcześniej, warto się zatrzymać i pokontemplować go przez chwilę, np. przekonując się o jego poprawności dla $m$ (Oczywiście, w ogólnej wersji wzoru nie ma znaczenia, czym są konkretnie zbiory $Api$ i pozostaje on prawdziwy dla dowolnych zbiorów.)

Zatem kolejną rzeczą, którą musimy zbadać, są zbiory postaci $|Api$ Wszystkie liczby $|pi1,...,pil$ są pierwsze, więc jeżeli pewna liczba ma być podzielna przez wszystkie z nich, to musi być podzielna przez ich iloczyn (stwierdzenie odwrotne oczywiście też jest prawdziwe), co prowadzi nas do zależności

Api

Dzięki niej wzór (2) możemy wyrazić następująco:

P[u][k] = Q dp[u][ j] + Q Q (−1)ldp[u][ j]. j 1DlDm i1@...@il pi1⋯pilS j

(3)

Widać, że wielokrotnie spotykamy się tutaj z podobnymi sumami składników $|dp[u][ j],$ zatem wprowadzając oznaczenie $|S[u][i] = PiS jdp[u][j ],$ możemy przepisać wzór (3) w trochę milszej postaci:

P[u][k] = S[u][1] + Q Q (−1)lS[u][pi1⋯ pil]. 1DlDm i1@...@il

(4)

Zauważmy, że jeżeli mamy tablicę $|dp[u],$ to jesteśmy w stanie relatywnie szybko wyznaczyć tablicę $S[u].$ A konkretnie, aby obliczyć $|S[u][i],$ potrzebujemy wysumować $|M- i$ składników. Zatem wykonanie tego dla $i = 1,...,M$ będzie miało złożoność czasową

111 (1+++...+))). O 23M

Zastanówmy się teraz, jaką złożoność ma wyznaczanie $P [u][k]$ za pomocą wzoru (4). Zauważmy, że występują w nim jedynie składniki postaci $|S[u][i],$ gdzie $|i$ jest pewnym dzielnikiem $k.$ Ponadto nie wszystkie dzielniki uwzględniamy (tylko takie niepodzielne przez kwadraty liczb pierwszych), ale ta obserwacja nie jest nam potrzebna, aby uzyskać sensowne oszacowanie. Zatem, aby wyznaczyć wartości $P [u][k]$ dla $,k = 1,...,M$ musimy wysumować co najwyżej tyle składników, ile jest łącznie dzielników liczb $, 1,...,M$ ale ich liczba jest również rzędu $logM).O(M$ Aby szybko się dostać do tych składników, warto na samym początku programu dla każdej liczby od $1$ do $M$ spamiętać jej bezkwadratowe dzielniki.

Podsumowując, mając tablice $dp[ui]$ dla wszystkich synów wierzchołka $|v,$ możemy w czasie $logM) O(sM$ kolejno wyznaczyć tablice $|S[ui]$ i $|P[ui],$ co pozwoli nam skorzystać ze wzoru (1) do wyznaczenia $|dp[v].$ Zatem w sumarycznym czasie $logM) |O(nM$ możemy tą metodą wyznaczyć odpowiedź dla korzenia drzewa. Uruchamiając powyższy algorytm dla każdej możliwości wyboru korzenia, możemy rozwiązać zadanie w czasie $logM). O(n$ Jednak autorów zadania taka złożoność nie satysfakcjonuje i wymagane jest rozwiązanie $logM).O(nM$

Pomysł pozwalający obliczać nam kompletne informacje dla wszystkich wierzchołków drzewa (a nie tylko te uwzględniające wierzchołki z odpowiadających im poddrzew), polega na spychaniu informacji z korzenia w dół, przesyłając informacje z "naddrzewa". Niech $v$ będzie pewnym wierzchołkiem, a $w$ jego ojcem w drzewie. Pamiętamy, że tablica $dp |$ jest iloczynem odpowiednich wartości tablic $P |$ dla sąsiadów w poddrzewie, dlatego jeżeli mamy kompletną tablicę $dp[w], |$ to aby obliczyć wkład naddrzewa $|v$ o korzeniu w wierzchołku $w,$ powinniśmy podzielić wartości z tablicy $|dp[w]$ przez odpowiadające wartości z tablicy $|P[v],$ przeliczyć jeszcze raz wartości tablic $|S[w]$ i $P | [w]$ na podstawie nowych wartości $|dp[w]$ (tablice te teraz lekko zmieniają swoje znaczenie, gdyż zmieniamy zbiór sąsiadów, którzy są uwzględniani w ich liczeniu), co pozwala nam wyliczyć kompletną tablicę $dp[v] |$ (tzn. taką, w której uwzględniony jest też ojciec). Aby wyznaczyć kompletne $dp[v]$ na podstawie informacji z ojca, potrzebujemy wykonać stałą liczbę przeliczeń tablic, z których każde odbywa się w czasie $logM), O(M$ co daje algorytm o sumarycznej złożoności $logM). O(nM$