Omówienie zadania Wirus (II etap XXX OI)

Podzadanie 1: $d \leq 100$

W zadaniu mamy daną liczbę dni $d$ oraz "genotyp" wirusa, czyli tablicę o długości $n$ składającą się wyłącznie z liczb $0$ i $1$. Naszym celem jest stwierdzenie, jak będzie wyglądał genotyp wirusa po $d$ dniach, jeśli każdego dnia wirus mutuje, zmieniając genotyp z postaci $(X_1, X_2,\dots,X_n)$ na $(X_2, X_3,\dots, X_n, X_1 \oplus X_2)$, gdzie symbolem $\oplus$ oznaczamy operację logiczną XOR.

Najprostszym i intuicyjnym podejściem do rozwiązania tego problemu jest naiwna symulacja procesu zgodnie z opisem zawartym w zadaniu. Polega to na stopniowym obliczaniu zmiany genotypu z dnia na dzień. W tym celu każdego dnia tworzymy nową tablicę, którą uzupełniamy zgodnie z regułą podaną w treści zadania.

Złożoność czasowa takiego rozwiązania wynosi $O(d \cdot n)$, ponieważ dla każdego dnia będziemy musieli skonstruować nową tablicę o długości $n$, a każdą jej komórkę obliczamy w czasie stałym (operacja XOR działa w czasie stałym).

Podzadanie 2: $d \leq 2\,000\,000$

Aby rozwiązać zadanie dla większej liczby dni, musimy dokonać pewnych obserwacji. Chcemy symulować zmiany ciągu szybciej, "pomijając" niektóre dni i obliczając wartości tablicy tylko wtedy, kiedy są nam absolutnie potrzebne. W tym celu spójrzmy jeszcze raz na to, jak przekształca się ciąg. Jeśli, po jednym dniu, z $(X_1, X_2,\dots,X_n)$ otrzymujemy $(X_2, X_3,\dots, X_n, X_1 \oplus X_2)$, to po dwóch otrzymamy $(X_3, X_4,...,X_n, X_1\oplus X_2, X_2\oplus X_3)$. Można zauważyć, że ciąg $(X_1, X_2,\dots,X_n)$ po $n-1$ dniach przekształci się na $ (X_n, X_1 \oplus X_2, X_2 \oplus X_3, \dots, X_{n-1} \oplus X_{n}) $. Następnie, po jeszcze jednym dniu, będzie miał on postać: $(X_1\oplus X_2, X_2 \oplus X_3, \dots, X_n \oplus (X_1 \oplus X_2)) $. Stąd łatwo jest obliczyć wartości w tablicy po $n$ dniach. Nie trzeba się martwić kolejnością operacji w przypadku ostatniej komórki, ponieważ XOR jest operacją łączną i przemienną.

Ciąg po $n$ dniach będzie dany wzorem: $ X_i = \begin{cases} X_i \oplus X_{i+1} & \text{ dla } i < n\\ X_n \oplus (X_1 \oplus X_2) & \text{ dla } i = n \end{cases} $

Mając dostępny taki wzór możemy wykonywać obliczenia dla $n$ dni jednocześnie, zmniejszając liczbę operacji wymaganych do uzyskania ostatecznego wyniku. Póki to możliwe, będziemy wykonywać kroki po $n$ dni na raz. Dopiero kiedy zostanie nam mniej niż $n$ dni, dokończymy symulację w sposób, w jaki robiliśmy to w poprzednim rozwiązaniu.

Złożoność czasowa takiego rozwiązanie wynosi $O(d + n^2)$, ponieważ wykonamy $\lfloor \frac{d}{n}\rfloor$ + $d\,\text{mod}\,n $ pełnych przekształceń tablicy, każde z których zajmuje $O(n)$ czasu.

Podzadanie 3: $n \leq 100$

W tym podzadaniu górne ograniczenie na liczbę dni, które musimy zasymulować, wynosi $10^{15}$. Liczba dni jest tak duża, że nie mieści się w zmiennej typu $\verb|int| $ i trzeba użyć typu $\verb|long long|$, aby wczytać dane. Widać, że poprzednie rozwiązanie jest zdecydowanie zbyt wolne dla tak dużych wartości $d$. Aby dalej usprawnić symulację procesu, należy użyć szybkiego potęgowania macierzy.

Jeśli czytelnik nie jest zaznajomiony z mnożeniem macierzy, wyjaśnienie jak ono działa można znaleźć (w języku angielskim) na przykład na tej stronie. Natomiast algorytm szybkiego potęgowania jest opisany tutaj. Dalsza część omówienia zakłada podstawowe zrozumienie mnożenia macierzy oraz znajomość algorytmu szybkiego potęgowania.

Od tego momentu będziemy używać oznaczenia $(X_1, X_2, \dots, X_n)^T$ do oznaczania wektorów pionowych. Dlaczego szybkie potęgowanie macierzy? Zwyczajne mnożenie (od lewej) wektora przez odpowiednio dobraną macierz pozwala nam przekształcić go na dowolną kombinację liniową jego elementów. Na przykład, dla wektora $v = (X_1, X_2, \dots, X_n)^T$ zawsze możemy dobrać taką macierz $M$ rozmiaru $ n\times n$, że wynikiem mnożenia $M \times v $ będzie wektor pionowy długości $n$, którego każdy element będzie dowolnie wybraną sumą wielokrotności wartości w $v$. Na przykład dla liczb Fibonacciego możemy mieć wektor $f = (F_n, F_{n+1})^T$, oraz macierz $ M = \tiny{\begin{bmatrix} 0&1\\ 1&1 \end{bmatrix}}$. Wtedy $ M\times f = (F_{n+1}, F_n+F_{n+1})^T $, co z definicji liczb Fibonacciego jest po prostu równe $(F_{n+1}, F_{n+2})^T$. W ten sposób uzyskujemy sposób na obliczenie kolejnej liczby Fibonacciego znając $2$ poprzednie. Czyli jeśli chcemy uzyskać n-tą liczbę Fibonacciego, wystarczy pomnożyć wektor $f$ zawierający $2$ pierwsze liczby Fibonacciego przez macierz $M^{n-1}$ i wziąć pierwszy element z wektora będącego wynikiem tego mnożenia. Używając szybkiego potęgowania możemy obliczyć macierz $M^{n-1}$ w czasie logarytmicznym, co sprawia, że możemy obliczyć n-tą liczbę Fibonacciego w czasie $O(\log(n))$.

Pojawia się jednak jeden problem - elementy nowego ciągu, na który chcemy przekształcać stary, nie są wyznaczane za pomocy sumy ważonej, a zamiast tego używają operacji XOR. Jednakże nie jest to problem, ponieważ $X_1 \oplus X_2 = (X_1 + X_2) \text{ mod }2$ dla $X_1,X_2\in\{0, 1\}$, czyli XOR jest równoważny z dodawaniem pod modulo $2$. W takim przypadku macierz $M $, przekształcająca wektor $(X_1, X_2, \dots, X_n)^T$ na $(X_2, X_3, \dots, X_1 \oplus X_2)^T $ będzie wyglądała następująco (przykład dla $n=4$): $$ \begin{bmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 1 & 0 & 0 \end{bmatrix} $$ Aby skonstruować macierz przekształcenia dla dowolnego $n$, będziemy kierować się następującymi zasadami:

Pierwsze dwa elementy ostatniego wiersza są równe $1$.
Dla $i \neq n$ i-ty wiersz ma wartość $1$ na pozycji i+1 (zakładając, że elementy macierzy numerujemy od 1 do n).
Wszystkie pozostałe elementy mają wartość $0$.

Uwaga implementacyjna: dla macierzy odpowiednikiem liczby $1$ jest macierz jednostkowa odpowiedniego rozmiaru.

Rozwiązanie tego typu będzie miało złożoność $O(n^3\log(d))$, ponieważ mnożenie macierzy o wymiarach $n$ na $n$ zajmuje $O(n^3)$ czasu, a wykonamy $O(\log(n))$ mnożeń.

Rozwiązanie wzorcowe

Aby uzyskać pełne $100$ punktów za rozwiązanie użyjemy tej samej metody, jednakże znacząco przyspieszymy mnożenie macierzy. Zwyczajne mnożenie macierzy, które zostało zastosowane w poprzednim rozwiązaniu, ma złożoność $O(n^3)$. Istnieją skomplikowane algorytmy, pozwalające na zmniejszenie tej złożoności nawet do około $O(n^{2.375})$, jednakże nasze rozwiązanie nie będzie z nich korzystać. Zamiast tego wykorzystamy fakt, że jedynymi wartościami w naszych macierzach będą liczby $0$ oraz $1$, a operacje, które na nich wykonamy są operacjami logicznymi. W takiej sytuacji, jeśli używamy zwyczajnych zmiennych int (zazwyczaj 32-bitowych), marnujemy dużo czasu i pamięci wykonując na nich operacje, które tak naprawdę powinny być wykonywane tylko na jednym bicie. Nawet zmienna typu $\verb|bool|$ zajmuje zazwyczaj $8$ bitów. Usprawnienia jakie wykonamy nie zmienią złożoności asymptotycznej programu, jednak zdecydowanie skrócą czas, w jakim mnożymy macierze.

Aby pomnożyć macierze szybko, skorzystamy z bitsetów (w C++). Za każdym razem, kiedy będziemy wykonywać mnożenie macierzy $A\cdot B$, będziemy tworzyć dwie tablice bitsetów: jedną na wiersze macierzy $A$, drugą na kolumny macierzy $B$. Zauważmy, że kiedy jedynymi możliwymi wartościami są $0$ i $1$, mnożenie można zastąpić operatorem logicznym &.

Aby obliczyć element wyniku mnożenia macierzy na pozycji $i, j$ będziemy brać i-ty wiersz pierwszej macierzy i j-tą kolumnę drugiej. Teraz aby uzyskać wynik, najpierw wykonamy operację & na reprezentujących je bitsetach. Następnie, aby uzyskać ostateczny wynik, weźmiemy resztę z dzielenia przez 2 liczby jedynek w bitsecie będącym wynikiem tej operacji. W C++ użyjemy do tego zwyczajnie operatora & oraz wbudowanej w bitset funkcji count. Bitowy & zastępuje nam mnożenie każdego wyrazu w wierszu przez odpowiadający mu wyraz w kolumnie. Funkcja count natomiast pozwala nam na bardzo szybkie sprawdzenie, ile jedynek jest w naszym wynikowym bitsecie. Jest to dokładnie nasza suma, z której wystarczy tylko wziąć resztę z dzielenia przez $2$, aby uzyskać wynik. Ważne jest jednak to, aby nie iterować się ręcznie po bitach w celu zliczenia jedynek, ponieważ zniweluje to jakiekolwiek zyski czasowe, które uzyskamy poprzez zastosowanie bitsetu.

Poprawnie zaimplementowane rozwiązanie działające w ten sposób uzyska pełne $100$ punktów.

Opis przygotowano w ramach projektu "Mistrzostwa w Algorytmice i Programowaniu - Uczniowie" - zadania finansowanego ze środków Ministerstwa Cyfryzacji.