http://spoj.com/ALGOLIGA/problems/AL_12_12
http://pl.spoj.com/problems/AL_12_12
Skrócony opis problemu:
Mamy sobie koło, na którym jest $n$ równo-oddalonych od siebie punktów. Z każdego punktu może wyskoczyć epicykloidor i poruszając się o jakąś odległość $l_i$ może przemieścić się do dowolnego innego punktu. Mamy również daną listę wszystkich możliwych $l_i$ - jest ich $m$. Głuchy telefon polega na tym, że z punktu $a$ wyskakuje epicykloidor o jakimś $l_i$ i wskakuje do punktu oddalonego o $l_i$. Z tego punktu wyskakuje kolejny epicykloidor (możliwe, że o innym $l_j$) i wskakuje do punktu oddalonego o $l_j$. I tak aż osiągnie się punkt $b$. Dla każdego z $q$ zapytań należy wypisać liczbę możliwych ścieżek (nie dróg!) z punktu $a$ do punktu $b$ o długości $x$ skoków. (Będąc w punkcie $b$ epicykloidor może potraktować go jako punkt pośredni, a nie końcowy i wykonać jeszcze kilka skoków przed zakończeniem rundy w punkcie $b$). Punkty są mają wartości rosnące zgodnie z kierunkiem ruchu wskazówek zegara. Wynik należy podać modulo 1010101.
Rozwiązanie:
Doświadczony algorytmik od razu gdy słyszy "ilość ścieżek z skądś dokądś o długości jakiejś" widzi macierz sąsiedztwa grafu. Jeśli weźmiemy bowiem macierz sąsiedztwa grafu G i podniesiemy ją do potęgi $x$, to otrzymamy dla każdej pary wierzchołków ilość ścieżek między nimi o długości $x$. Tak też jest i tutaj. Do tego potrzebujemy jednak graf. Możemy go bardzo łatwo utworzyć. Wiemy, że z każdego punktu można wyjść na $m$ sposobów. Punkty potraktujmy zatem jako wierzchołki, a długości skoków jako długości krawędzi (nie wagi). A zatem dla wszystkich $n$ wierzchołków $a_i$ oraz $m$ długości skoków $l_j$ dodamy do grafu krawędź $a_i \rightarrow (a_i+l_j) \mod n$. Ów wzór nie będzie nam jednak działał dla numeracji wierzchołków $1..n$, więc rzutujemy to na przedział $0..n-1$. Oczywiście nie trzeba tego robić, ale należy wtedy wyifować przypadek, w którym owa wartość jest równa 0 i zamienić wartość na $n$. A zatem, mamy sobie graf z $n \cdot m$ krawędziami, a raczej jego macierz sąsiedztwa.
Pozostaje nam spotęgować ową macierz do potęgi $x$ dla każdego zapytania. Pomyślmy ile będzie nas to kosztować. Jeśli skorzystamy z algorytmu szybkiego potęgowania, to wykonamy $log_2 x$ operacji mnożeń macierzy. Mnożenie macierzy wykonuje się z kolei w czasie $O(n^3)$ (korzystając oczywiście z algorytmu brutalnego; najlepsza złożoność to $O(2^{2.3727})$, ale nie o to w tym zadaniu chodziło, żeby ją implementować). Mamy zatem około $q \cdot n^3 \cdot log_2 x$ operacji. Przy dodatkowym warunku z zadania $\max(n,m) \cdot q \le 5000$ wychodzi nam $5000 \cdot 5000 \cdot 30 = 75 \cdot 10^7$ operacji, a więc trochę sporo. Jak możemy zmniejszyć tę ilość? Szybkiego potęgowania nie przeskoczymy. Dla każdego zapytania musimy osobno obliczać ową macierz, gdyż mamy różne $x$. Pozostaje nam zatem... szybciej mnożyć macierze. Ale jak, skoro napisałem, że w zadaniu nie chodzi o pisanie wysublimowanego i skomplikowanego algorytmu mnożenia macierzy? Ano można coś zauważyć, co pozwoli na pomnożenie dwóch macierzy w czasie kwadratowym!
Spójrzmy sobie na naszą macierz (dla $n=6$, by mieć pewność, że to co zauważyliśmy nie jest tylko przypadkiem). Okazuje się, że nasza macierz jest... macierzą cykliczną! Innymi słowy, każdy wiersz jest przesunięciem poprzedniego wiersza (lub ostatniego, dla wiersza pierwszego) o 1 w prawo. Jak może nam to pomóc? Ano tak, że potęga takiej macierzy jest również macierzą cykliczną. Co za tym idzie, potrzebujemy tylko 1 wiersz z tej macierzy i na jego podstawie możemy otrzymać pozostałe wiersze. Mnożenie wierszy zajmie nam tylko $O(n^2)$.
Możemy mnożyć macierz w $O(n^2)$, a potem przepisywać pierwszy wiersz na pozostałe $n-1$ wierszy również w $O(n^2)$ nie tracąc na złożoności, lecz nie ma to większego sensu. Możemy bowiem do końca operować jedynie na 1 wierszu, a na koniec odwołać się do odpowiedniej jego komórki. Wzór na właściwą komórkę jest może trochę bardziej złożony, ale za to oszczędzamy znacznie na pamięci! Schodzimy z $O(n^2)$ na $O(n)$ pamięci. Poza tym stała nam się zmniejsza przy złożoności czasowej. Również tworzenie macierzy (a raczej listy) sąsiedztwa będzie trwało jedynie $O(m)$ czasu zamiast $O(n \cdot m)$.
Dodatkową trudnością w tym zadaniu jest wymóg jednej optymalizacji niższego rzędu. Interesuje nas bowiem wynik modulo 1010101 (jako że ilości ścieżek są dosyć spore). Przy mnożeniu macierzy musimy więc pamiętać by wykonać operację modulo. Obliczanie każdej komórki w pierwszym wierszu trwa $O(n)$ czasu. Jeśli po każdej jej modyfikacji programista będzie wykonywał operację modulo, dostanie TLE (time limit exceeded). Można bowiem ustawić typ wiersza na long longa i dopiero po obliczeniu całej komórki wykonać operację modulo. Wykonamy wtedy jedynie 1 modulo zamiast $n$. Taka optymalizacja może wydawać się śmieszna, jednak daje naprawdę dużo. Dla rozwiązania z czasem ~7.5s wersja z $n$ operacjami modulo wykonuje się ponad... 40s! Warto pamiętać o tej sztuczce.
Poniżej znajduje się iteracyjna wersja algorytmu szybkiego sortowania, a pod nią rekurencyjny odpowiednik.
Złożoność: $O(q \cdot n^2 \cdot log_2 x)$.
Algorytm:
int main()
{
int t, n, m, x, a, b, r, q, i, j;
long long in[MAX_N], out[MAX_N], tmp[MAX_N], in2[MAX_N];
get(t);
while(t--)
{
get(n, m, q);
for(i = 0; i < n; ++i)
in[i] = 0;
while(m--) // tworzymy pierwszy wiersz listy sąsiedztwa
get(x),
++in[x%n];
while(q--)
{
get(a, b, r);
--a; --b; // rzutujemy przedział
for(i = 0; i < n; ++i) // w in2 jest kopia pierwszego wiersza, gdyż go modyfikujemy w każdym zapytaniu, a powinien być on niezależny od zapytań; w out będziemy mieli wiersz wynikowy
out[i] = 0,
in2[i] = in[i];
out[0] = 1; // w iteracyjnym algorytmie szybkiego potęgowania początkowa wartość wynosi 1, gdyż jest to element neutralny ze względu na mnożenie ($1 \cdot x = x$); macierzowym odpowiednikiem jest macierz jednostkowa, a jej pierwszy wiersz składa się z 1 na początku oraz samych zer
while(r) // dopóki wykładnik jest niezerowy
{
if(r&1) // jeśli wykładnik jest nieparzysty: out *= in2
{
for(i = 0; i < n; ++i)
for(tmp[i] = j = 0; j < n; ++j)
tmp[i] += out[j]*in2[n-j+i < n ? n-j+i : i-j]; // optymalizacja dla in2[(n-j+i)%n]
for(i = 0; i < n; ++i) // nie możemy robić modulo w poprzedniej pętli, gdyż korzystamy ze starych wartości out[]
out[i] = tmp[i]%MOD;
}
// in2 = in2^2
for(i = 0; i < n; ++i)
for(tmp[i] = j = 0; j < n; ++j)
tmp[i] += in2[j]*in2[n-j+i < n ? n-j+i : i-j]; // optymalizacja dla in2[(n-j+i)%n]
for(i = 0; i < n; ++i)
in2[i] = tmp[i]%MOD;
r >>= 1; // optymalizacja dla r /= 2
}
print(out[a ? (b+n-a)%n : b]);
}
}
}
Wersja rekurencyjna:
int n;
struct MatrixRow
{
long long x[MAX_N];
MatrixRow& operator=(const MatrixRow &a)
{
for(int i = 0; i < n; ++i)
x[i] = a.x[i];
return *this;
}
} in, out;
MatrixRow matrix_mul(MatrixRow a, MatrixRow b)
{
MatrixRow c;
for(int i = 0; i < n; ++i)
{
c.x[i] = 0;
for(int j = 0; j < n; ++j)
c.x[i] += a.x[j]*b.x[n-j+i < n ? n-j+i : i-j];
c.x[i] %= MOD;
}
return c;
}
MatrixRow matrix_pow(MatrixRow a, int r)
{
if(r < 2)
return a;
if(r&1) // r jest nieparzyste
return matrix_mul(a, matrix_pow(a, r-1));
MatrixRow c = matrix_pow(a, r>>1); // r/2
return matrix_mul(c, c);
}
int main()
{
int t, m, x, a, b, r, q, i, j;
get(t);
while(t--)
{
get(n, m, q);
for(i = 0; i < n; ++i)
in.x[i] = 0;
while(m--) // twórz pierwszy wiersz macierzy sąsiedztwa
get(x),
++in.x[x%n];
while(q--)
{
get(a, b, r);
--a; --b; // rzutuj przedział wierzchołków
out = matrix_pow(in, r); // potęguj pierwszy wiersz macierzy sąsiedztwa
print(out.x[a ? (b+n-a)%n : b]);
}
}
}
Brak komentarzy:
Prześlij komentarz