Autorem tego wpisu jest Szymon Krzywda — pasjonat informatyki i aktywny zawodnik w konkursach algorytmicznych. Szymon został powołany do reprezentacji Polski na European Junior Olympiad in Informatics (EJOI). Jest laureatem III stopnia Olimpiady Informatycznej (OI) oraz dwukrotnym laureatem I stopnia Olimpiady Informatycznej Juniorów (OIJ). Swoją przygodę z olimpiadami rozpoczął w 7. klasie szkoły podstawowej jako samouk — już wtedy udało mu się awansować do finału OIJ.

W tej serii wpisów proponowane są ciekawe zadania wraz z opisem rozwiązań. Zachęcam do zajrzenia do poprzednich wpisów z tej serii. W tym tygodniu zajmiemy się zadaniem Graph Traveler z Codeforces.

Treść zadania

Zadanie, wraz z treścią, można rozwiązywać tutaj. Również napiszę skrót treści.

Danych jest $N \le 1\,000$ wierzchołków. Każdy wierzchołek ma $m_{i}$ sąsiadów $1 \le m_{i} \le 10$, oznaczonych przez $e_{i}[0], e_{i}[1], …, e_{i}[m_{i} - 1]$ i pewną liczbę $k_{i}$.

Podróż w tym grafie wygląda następująco:

  1. Wybieramy pewien wierzchołek i liczbę $c$.
  2. Gdy odwiedzimy wierzchołek $v$, to dodajemy $k_{v}$ do $c$.
  3. Odwiedzamy teraz wierzchołek $e_{v}[x]$, który spełnia $x ≡ c \mod m_{i}$.

Jest oczywiste, że taka podróż trwa w nieskończoność. Mamy również $1 \le Q \le 10^5$ zapytań, na dane zapytanie masz odpowiedzieć, ile wierzchołków odwiedzimy nieskończenie wiele razy, jeżeli zaczynamy z wierzchołka $v$ z pewną liczbą $c$.

Zanim przejdziesz do przeczytania rozwiązania, spróbuj samemu pomyśleć nad rozwiązaniem przez pewien czas. Jeśli Ci się nie uda — wtedy wróć tutaj.

Podpowiedzi

Zanim przejdziemy do pełnego rozwiązania, rozważmy kilka podpowiedzi.

Podpowiedź #1

Czy możemy jakoś przygotować się na zapytania preprocessingiem?

Podpowiedź #2

Jeżeli chcemy poznać wynik dla każdego wierzchołka i modulo, to jakie informacje musimy trzymać w stanie? Jak będą wyglądać przejścia?

Podpowiedź #3

Czy możemy jakoś zmniejszyć ilość informacji w stanie?

Podpowiedź #4

$l ≡ r ~ (mod ~ a \cdot b) ~ \Rightarrow ~ r ≡ l ~ (mod ~ a)$
Innymi słowy, jeżeli znamy resztę z dzielenia liczby $x$ przez $10$, to również możemy szybko poznać resztę dzielenia tej liczby przez $5$.

Rozwiązanie

Spróbujmy jakoś policzyć wynik dla każdego wierzchołka, zanim dostaniemy zapytania.

W stanie potrzebowalibyśmy trzymać numer aktualnego wierzchołka i informacje o aktualnych resztach. Oznaczmy $dp[v][r2][r3][r4][r5][r6][r7][r8][r9][r10]$ — jako wynik dla wierzchołka $v$, gdy nasza aktualna reszta dzielenia liczby $c$ przez $2$ wynosi $r2$, reszta dzielenia przez $3$ wynosi $r3$ i tak dalej.

Zauważmy, że jeżeli znamy resztę z dzielenia przez $10$, to również znamy resztę dzielenia przez $5$ i $2$. Dokładniej, jeżeli znamy resztę z dzielenia przez $x$, to również znamy reszty dzielenia przez wszystkich dzielników $x$.

Jak otrzymać tę resztę?
Jeżeli reszta z dzielenia liczby przez $x$ wynosi $r$ i chcemy uzyskać resztę dzielenia tej liczby przez któregoś z dzielników $x$ — oznaczę ten dzielnik przez $d$, to wystarczy sprawdzić resztę z dzielenia liczby $r$ przez $d$.
Weźmy na przykład liczbę $17$, reszta z dzielenia liczby $17$ przez $10$ wynosi $7$. By otrzymać resztę z dzielenia przez $5$, wystarczy sprawdzić resztę dzielenia przez $5$ z liczby $7$, która wynosi $2$. Widzimy, że to się zgadza: $17 ≡ 2 ~ (mod ~ 5)$.

Teraz spróbujmy zamiast trzymać reszty z dzielenia przez $2, 3, 4, …, 10$, trzymać mniej lub nawet jedną resztę z dzielenia, tak byśmy mogli łatwo uzyskać reszty z dzielenia przez $2, 3, 4, …, 10$. Zauważmy, że jeżeli trzymamy informację o resztach, to dla każdej liczby od $2$ do $10$, co najmniej jedna z tych reszt musi być przez tę liczbę podzielna, by uzyskać informację o tej reszcie.

Spróbujmy trzymać tylko jedną resztę dzielenia przez $l$. Zauważmy, że $l$ musi być podzielne przez $2, 3, 4, …, 10$. Z oczywistych względów chcielibyśmy również, żeby $l$ było jak najmniejsze, więc kandydatem na $l$ jest NWW liczb $2, 3, 4, …, 10$. NWW liczb od $2$ do $10$ wynosi $2520$.

Widzimy teraz, że w stanie wystarczy nam informacja o aktualnym wierzchołku i reszcie z dzielenia liczby $c$ przez $2520$ — $dp[v][r2520]$.

Możemy teraz puszczać DFS-a z każdego wierzchołka, gdy nasza reszta wynosi kolejno $0, 1, 2, …, 2519$ i liczyć wynik. Jeżeli jesteśmy aktualnie w wierzchołku $v$ i mamy resztę $r$, to wystarczy dodać do naszej aktualnej reszty $k_{i}$ i potem przejść DFS-em do następnego wierzchołka i policzyć również dla niego wynik. Nasz wynik będzie jemu równy.

Jeżeli zobaczymy, że dany wierzchołek już odwiedziliśmy, to mamy dwa przypadki:

  1. Odwiedziliśmy go nie w tym DFS-ie i mamy już dla niego policzony wynik, więc możemy zawrócić DFS-a.
  2. Odwiedziliśmy go w tym DFS-ie i liczymy teraz dla niego wynik — robimy to tak, że trzymamy dodatkowo na stosie stany, które odwiedziliśmy do tego momentu i dopóki nie zobaczymy na szczycie stosu naszego stanu, to liczymy, ile jest różnych wierzchołków do tego momentu.

Więcej o szukaniu cykli można przeczytać tu

Każdy stan odwiedziliśmy i liczyliśmy maksymalnie raz, więc nasza złożoność wynosi $\mathcal{O}(2520N)$.