https://spoj.com/ALGOLIGA/problems/AL_16_04
https://pl.spoj.com/problems/AL_16_04
Skrócony opis problemu:
Mamy dane $t$ testów - każdy składa się z: $n$ i $m$ oraz 3 punktów: $P_1$, $P_2$, $P_3$. Zaczynając od punktu $(1, 1)$ i mogąc się poruszać tylko w prawo lub górę (czyli mogąc tylko zwiększać jedną ze współrzędnych) na ile sposobów można dojść do punktu $(n, m)$ tak, żeby przejść przez przynajmniej 1 punkt z 3 danych. Należy podać liczbę sposobów modulo $10^9+7$.
Rozwiązanie naiwne:
Możemy sprawdzić każdą możliwą drogę i zliczyć tylko te, które zawierają 1 z punktów.
Złożoność: wykładnicza. Mógłbym podać dokładny wzór, ale byłby to spoiler rozwiązania wzorcowego. O nim potem.
Rozwiązanie sprytniejsze:
Powiedzmy, że chcemy sprawdzić na ile sposobów możemy dojść z punktu $(1, 1)$ do $(5, 4)$. Ile wynosi owa liczba? Ano mamy 2 opcje: albo pójdziemy w górę, albo w prawo. Wynikiem będzie więc suma wartości dla punktów $(1, 2)$ oraz $(2, 1)$. Dla nich możemy zrobić to samo. Mamy zatem tutaj do czynienia z prostym programowaniem dynamicznym. Każdej komórce $(i, j)$ przypisujemy sumę komórek $(i-1, j)$ i $(i, j-1)$, gdyż tylko z nich możemy do niej dojść. Na początku oczywiście ustawiamy wartość komórek o którejkolwiek współrzędnej 0 na 1 (bo do skrajnych komórek po lewej stronie i na dole możemy się dostać tylko na 1 sposób - idąc cały czas w prawo albo cały czas w górę). Po obliczeniu każdej komórki wykonujemy na niej operację modulo, by mieścić się w standardowym typie zmiennych.
Dla każdego z $t$ testów możemy wtedy w czasie stałym obliczyć na ile sposobów dojść z jednego punktu do drugiego. Ale przecież musimy wybrać jedynie drogi przechodzące przez przynajmniej jeden z tych 3 punktów. No i jak to zrobić? Wystarczy dla każdego z 3 punktów odczytać z tabeli na ile sposobów można do niego dojść z punktu $(1, 1)$ oraz na ile sposobów można dojść z tego punktu do $(n, m)$ i obie wartości pomnożyć (i wykonać operację modulo). No i oczywiście sumujemy owe 3 iloczyny (i znów modulo).
Ale czy przypadkiem nie policzymy niektórych dróg więcej niż raz? Owszem. Drogi przechodzące przez 2 i 3 punkty policzymy więcej niż raz, bo zrobimy to dla każdego punktu. Jak to rozwiązać? Ano kłania się tutaj zasada włączeń i wyłączeń. Wystarczy dla każdej pary punktów odjąć od wyniku liczbę dróg, które przechodzą przez oba punkty a na końcu dodać liczbę dróg, które przechodzą przez wszystkie 3 punkty. Czemu tak? Ano spójrzmy sobie na obrazek z Wikipedii:
Niech $A$, $B$ i $C$ będą odpowiadały liczbom dróg przechodzących przez $P_1$, $P_2$ i $P_3$. Jeśli zsumujemy je wszystkie to będziemy mieli 2 razy drogi przechodzące przez 2 z 3 punktów i 3 razy drogi przechodzące przez wszystkie 3 punkty. Jeśli odejmiemy dla każdej pary drogi przechodzące przez owe 2 punkty to wyzerujemy również środek diagramu, więc trzeba będzie dodać na nowo drogi przechodzące przez 3 punkty. Należy przy każdym dodawaniu i odejmowaniu wykonywać operację modulo. Przy odejmowaniu może się zdarzyć, że uzyskamy liczbę ujemną (operacja modulo niekoniecznie zwraca bowiem liczby dodatnie). Wystarczy wtedy dodać do wyniku $10^9+7$ i wszystko będzie się zgadzać.
Złożoność: $O(n \cdot m + t)$, bo na początku wypełniamy $n \cdot m$ komórek macierzy, a potem dla każdego z $t$ testów wykonujemy $x^2-x+1$ dodawań lub odejmowań, gdzie $x$ to ilość punktów. W naszym przypadku $x$ jest stałe i wynosi 3, więc owy współczynnik pomijamy. Złożoność pamięciowa: $O(n \cdot m)$, bo potrzebujemy macierzy takiego rozmiaru, żeby trzymać te ilości dróg.
Rozwiązanie najsprytniejsze:
W poprzednim rozwiązaniu dla każdego testu wykonujemy stałą ilość operacji. Możemy więc tylko poprawić złożoność preprocessingu, czyli tego co wykonujemy na początku tylko raz. Przyjrzyjmy się zatem naszym liczbom dróg.
Weźmy sobie na początku prostokąty o szerokości 1 (nie 0). Są nimi np. (1;1)-(2;2), (1;1)-(3;2), (5,5)-(8,6). Najłatwiej jest je rysować w zeszycie w kratkę. No więc dla takiego prostokąta o szerokości i długości 1 mamy oczywiście 2 drogi. Dla długości 2 mamy 3 drogi. Dla długości 3 mamy 4 drogi. Można więc łatwo zauważyć, że $a_{1,j} = j+1$.
Teraz weźmy sobie szerokość 2. Dla szerokości i długości 2 mamy 6 dróg. Dla długości 3 mamy 6+4=10 dróg (bo dodajemy 2x2 + 1x3 jak w poprzednim rozwiązaniu). Dla długości 4 mamy 10+5=15 dróg. Dla 5 15+6=21 dróg. Dla 6 21+7=28 dróg. Otrzymujemy ciąg: $6, 10, 15, 21, 28, \ldots$. Coś przypomina? Ano dodajemy za każdym razem kolejno $4, 5, 6, 7, \ldots$ do poprzedniej wartości. A zatem będą to liczby trójkątne, określone wzorem: $\frac{n \cdot (n+1)}{2} = \binom{n+1}{2}$. Podstawiając $n=7$ otrzymamy 28, które jest liczbą dróg dla szerokości 2 i długości 6. A zatem trzeba do $n$ dodać jeszcze 1. Otrzymujemy wtedy $a_{2,j} = \frac{(j+1) \cdot (j+2)}{2} = \binom{j+2}{2}$.
Następnie szerokość 3. Dla 3x3 mamy 10+10=20 (2x3 + 2x3). Dla 3x4 mamy 20+15=35 (3x3 + 2x4). Dla 3x5 - 35+21=56. 3x6 - 56+28=84. Otrzymujemy ciąg: $20, 35, 56, 84, \ldots$. Od razu widać, że... nic nie widać po nim. No ale jeśli wkleimy go na OEIS, to okaże się, że są to liczby czworościenne, dane wzorem $\frac{n \cdot (n+1) \cdot (n+2)}{6} = \binom{n+2}{3}$. Dla $n=7$ otrzymamy 84. Znów więc trzeba będzie dodać 1 do $n$. Czyli nasz kolejny wzór to $a_{3,j} = \frac{(j+1) \cdot (j+2) \cdot (j+3)}{3} = \binom{j+3}{3}$.
Wystarczy. Spójrzmy na wszystkie 3 wzory? Widać coś podobnego? No na pewno nie przy ułamkowych wzorach. Ale wzory dla szerokości 2 i 3 mają bardzo podobne wzory wyrażone symbolem Newtona. A co gdybyśmy spróbowali przedstawić pierwszy wzór za pomocą owego symbolu? Byłoby to $a_{1,j} = \binom{n+1}{1}$. Myślę, że większość już zauważyła zależność. Wzór ogólny to zatem $a_{i,j} = \binom{i+j}{i} = \binom{i+j}{j}$. Owa druga część jest skutkiem symetryczności symbolu Newtona ($\binom{n}{k} = \binom{n}{n-k}$).
No dobra, mamy wzór, ale musielibyśmy go obliczyć dla każdego testu w czasie stałym, żeby cokolwiek zoptymalizować. A więc znów musielibyśmy obliczyć około $n \cdot m$ symboli Newtona? Nie! Nie będziemy korzystać z wzorów rekurencyjnych na symbol Newtona, ale z jego definicji, czyli $\binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}$. No ale silnię modulo liczy się w czasie liniowym, bo trzeba wykonać $n$ mnożeń. Tak, ale... $n$ silni również liczy się w czasie liniowym, bo z każdym mnożeniem otrzymujemy kolejną silnię. Tak więc koszt zamortyzowany obliczenia silni jest stały jeśli chcemy ich dużo obliczyć. Wystarczy więc przed wczytaniem danych wykonać preprocessing, czyli obliczyć wszystkie silnie na początku i potem z nich korzystać. Zapisujemy więc w tablicy silnię modulo $10^9+7$ dla każdej liczby do maksymalnego $n$ (lub $m$). Ale chwila! Przecież będziemy musieli dzielić owe silnie. A wartości będą resztą z dzielenia przez $10^9$, a to znaczy, że możemy otrzymać liczby niecałkowite. Owszem, ale w arytmetyce modularne da się również zrealizować dzielenie całkowitoliczbowe. Samego dzielenia wprawdzie nie ma, ale jest... odwrotność. Robimy więc to samo co w zwykłej arytmetyce, czyli jeśli chcemy obliczyć $x \div y$, to możemy obliczyć $x \cdot \frac{1}{y}$, czyli $x \cdot y^{-1}$. Dzielenie jest bowiem operacją odwrotną do mnożenia, więc możemy pomnożyć jedną silnię przez odwrotność drugiej.
A jak szybko policzyć odwrotność z silni? Ano tak samo jak przy silni mnożymy przez kolejne liczby całkowite, tak będziemy mnożyć przez odwrotności kolejnych liczb całkowitych (wszystko to modulo $10^9+7$). A jak w ogóle policzyć odwrotność? Ano za pomocą rozszerzonego algorytmu Euklidesa, którego opisywać nie będę. Tak więc liczymy sobie silnię modulo oraz odwrotność silni modulo i zapisujemy je w 2 tablicach, a przy obliczaniu każdego symbolu Newtona wykonujemy 3 mnożenia (i 2 operacje modulo).
Optymalizacja: Zamiast wykonywać preprocessing dla maksymalnego $n$ (czyli $10^5$) możemy najpierw wczytać wszystkie dane i wyliczyć silnię dla maksymalnego $n$ z danych. Dla małych testów będziemy mieli wtedy znacznie mniejszy czas.
Złożoność: $O\left(\max(n,m) \cdot \log^2 MOD + t\right)$, bo na początku wykonujemy dla każdej z $n$ silni musimy obliczyć element odwrotny do kolejnych liczb naturalnych, a robimy to rozszerzonym algorytmem Euklidesa, który działa w czasie $O\left(\log^2 MOD\right)$ (gdzie $MOD=10^9+7$), a następnie dla każdego testu wykonujemy stałą ilość operacji, jak w poprzednim algorytmie. Złożoność pamięciowa: $O(\max(n,m))$.
Algorytm (który trzeba zmodyfikować uwzględniając 2 szczególne przypadki, z czego o 1 wspomniałem powyżej):
Niech $A$, $B$ i $C$ będą odpowiadały liczbom dróg przechodzących przez $P_1$, $P_2$ i $P_3$. Jeśli zsumujemy je wszystkie to będziemy mieli 2 razy drogi przechodzące przez 2 z 3 punktów i 3 razy drogi przechodzące przez wszystkie 3 punkty. Jeśli odejmiemy dla każdej pary drogi przechodzące przez owe 2 punkty to wyzerujemy również środek diagramu, więc trzeba będzie dodać na nowo drogi przechodzące przez 3 punkty. Należy przy każdym dodawaniu i odejmowaniu wykonywać operację modulo. Przy odejmowaniu może się zdarzyć, że uzyskamy liczbę ujemną (operacja modulo niekoniecznie zwraca bowiem liczby dodatnie). Wystarczy wtedy dodać do wyniku $10^9+7$ i wszystko będzie się zgadzać.
Złożoność: $O(n \cdot m + t)$, bo na początku wypełniamy $n \cdot m$ komórek macierzy, a potem dla każdego z $t$ testów wykonujemy $x^2-x+1$ dodawań lub odejmowań, gdzie $x$ to ilość punktów. W naszym przypadku $x$ jest stałe i wynosi 3, więc owy współczynnik pomijamy. Złożoność pamięciowa: $O(n \cdot m)$, bo potrzebujemy macierzy takiego rozmiaru, żeby trzymać te ilości dróg.
Rozwiązanie najsprytniejsze:
W poprzednim rozwiązaniu dla każdego testu wykonujemy stałą ilość operacji. Możemy więc tylko poprawić złożoność preprocessingu, czyli tego co wykonujemy na początku tylko raz. Przyjrzyjmy się zatem naszym liczbom dróg.
Weźmy sobie na początku prostokąty o szerokości 1 (nie 0). Są nimi np. (1;1)-(2;2), (1;1)-(3;2), (5,5)-(8,6). Najłatwiej jest je rysować w zeszycie w kratkę. No więc dla takiego prostokąta o szerokości i długości 1 mamy oczywiście 2 drogi. Dla długości 2 mamy 3 drogi. Dla długości 3 mamy 4 drogi. Można więc łatwo zauważyć, że $a_{1,j} = j+1$.
Teraz weźmy sobie szerokość 2. Dla szerokości i długości 2 mamy 6 dróg. Dla długości 3 mamy 6+4=10 dróg (bo dodajemy 2x2 + 1x3 jak w poprzednim rozwiązaniu). Dla długości 4 mamy 10+5=15 dróg. Dla 5 15+6=21 dróg. Dla 6 21+7=28 dróg. Otrzymujemy ciąg: $6, 10, 15, 21, 28, \ldots$. Coś przypomina? Ano dodajemy za każdym razem kolejno $4, 5, 6, 7, \ldots$ do poprzedniej wartości. A zatem będą to liczby trójkątne, określone wzorem: $\frac{n \cdot (n+1)}{2} = \binom{n+1}{2}$. Podstawiając $n=7$ otrzymamy 28, które jest liczbą dróg dla szerokości 2 i długości 6. A zatem trzeba do $n$ dodać jeszcze 1. Otrzymujemy wtedy $a_{2,j} = \frac{(j+1) \cdot (j+2)}{2} = \binom{j+2}{2}$.
Następnie szerokość 3. Dla 3x3 mamy 10+10=20 (2x3 + 2x3). Dla 3x4 mamy 20+15=35 (3x3 + 2x4). Dla 3x5 - 35+21=56. 3x6 - 56+28=84. Otrzymujemy ciąg: $20, 35, 56, 84, \ldots$. Od razu widać, że... nic nie widać po nim. No ale jeśli wkleimy go na OEIS, to okaże się, że są to liczby czworościenne, dane wzorem $\frac{n \cdot (n+1) \cdot (n+2)}{6} = \binom{n+2}{3}$. Dla $n=7$ otrzymamy 84. Znów więc trzeba będzie dodać 1 do $n$. Czyli nasz kolejny wzór to $a_{3,j} = \frac{(j+1) \cdot (j+2) \cdot (j+3)}{3} = \binom{j+3}{3}$.
Wystarczy. Spójrzmy na wszystkie 3 wzory? Widać coś podobnego? No na pewno nie przy ułamkowych wzorach. Ale wzory dla szerokości 2 i 3 mają bardzo podobne wzory wyrażone symbolem Newtona. A co gdybyśmy spróbowali przedstawić pierwszy wzór za pomocą owego symbolu? Byłoby to $a_{1,j} = \binom{n+1}{1}$. Myślę, że większość już zauważyła zależność. Wzór ogólny to zatem $a_{i,j} = \binom{i+j}{i} = \binom{i+j}{j}$. Owa druga część jest skutkiem symetryczności symbolu Newtona ($\binom{n}{k} = \binom{n}{n-k}$).
No dobra, mamy wzór, ale musielibyśmy go obliczyć dla każdego testu w czasie stałym, żeby cokolwiek zoptymalizować. A więc znów musielibyśmy obliczyć około $n \cdot m$ symboli Newtona? Nie! Nie będziemy korzystać z wzorów rekurencyjnych na symbol Newtona, ale z jego definicji, czyli $\binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}$. No ale silnię modulo liczy się w czasie liniowym, bo trzeba wykonać $n$ mnożeń. Tak, ale... $n$ silni również liczy się w czasie liniowym, bo z każdym mnożeniem otrzymujemy kolejną silnię. Tak więc koszt zamortyzowany obliczenia silni jest stały jeśli chcemy ich dużo obliczyć. Wystarczy więc przed wczytaniem danych wykonać preprocessing, czyli obliczyć wszystkie silnie na początku i potem z nich korzystać. Zapisujemy więc w tablicy silnię modulo $10^9+7$ dla każdej liczby do maksymalnego $n$ (lub $m$). Ale chwila! Przecież będziemy musieli dzielić owe silnie. A wartości będą resztą z dzielenia przez $10^9$, a to znaczy, że możemy otrzymać liczby niecałkowite. Owszem, ale w arytmetyce modularne da się również zrealizować dzielenie całkowitoliczbowe. Samego dzielenia wprawdzie nie ma, ale jest... odwrotność. Robimy więc to samo co w zwykłej arytmetyce, czyli jeśli chcemy obliczyć $x \div y$, to możemy obliczyć $x \cdot \frac{1}{y}$, czyli $x \cdot y^{-1}$. Dzielenie jest bowiem operacją odwrotną do mnożenia, więc możemy pomnożyć jedną silnię przez odwrotność drugiej.
A jak szybko policzyć odwrotność z silni? Ano tak samo jak przy silni mnożymy przez kolejne liczby całkowite, tak będziemy mnożyć przez odwrotności kolejnych liczb całkowitych (wszystko to modulo $10^9+7$). A jak w ogóle policzyć odwrotność? Ano za pomocą rozszerzonego algorytmu Euklidesa, którego opisywać nie będę. Tak więc liczymy sobie silnię modulo oraz odwrotność silni modulo i zapisujemy je w 2 tablicach, a przy obliczaniu każdego symbolu Newtona wykonujemy 3 mnożenia (i 2 operacje modulo).
Optymalizacja: Zamiast wykonywać preprocessing dla maksymalnego $n$ (czyli $10^5$) możemy najpierw wczytać wszystkie dane i wyliczyć silnię dla maksymalnego $n$ z danych. Dla małych testów będziemy mieli wtedy znacznie mniejszy czas.
Złożoność: $O\left(\max(n,m) \cdot \log^2 MOD + t\right)$, bo na początku wykonujemy dla każdej z $n$ silni musimy obliczyć element odwrotny do kolejnych liczb naturalnych, a robimy to rozszerzonym algorytmem Euklidesa, który działa w czasie $O\left(\log^2 MOD\right)$ (gdzie $MOD=10^9+7$), a następnie dla każdego testu wykonujemy stałą ilość operacji, jak w poprzednim algorytmie. Złożoność pamięciowa: $O(\max(n,m))$.
Algorytm (który trzeba zmodyfikować uwzględniając 2 szczególne przypadki, z czego o 1 wspomniałem powyżej):
int rev(int a)
{
int q, u = 1, w = a, x = 0, z = MOD;
while(w)
{
if(w < z)
q = u, u = x, x = q,
q = w, w = z, z = q;
q = w / z;
u -= q * x;
w -= q * z;
}
if(x < 0)
x += MOD;
return x;
}
int ways(int x, int y)
{
return fact[x+y]*rev_fact[y]%MOD*rev_fact[x]%MOD;
}
int main()
{
int t, n, m, x[9], y[9], z, ans, i, MOD = 1000000007, fact[200009], rev_fact[100009];
fact[0] = fact[1] = rev_fact[0] = rev_fact[1] = 1;
for(i = 2; i < 200001; ++i)
fact[i] = fact[i-1]*i%MOD;
for(i = 2; i < 100001; ++i)
rev_fact[i] = rev_fact[i-1]*rev(i)%MOD;
get(t);
while(t--)
{
get(n, m);
for(ans = i = 0; i < 3; ++i)
get(x[i], y[i]),
ans = (ans+ways(x[i]-1, y[i]-1)*ways(n-x[i], m-y[i]))%MOD; // dodajemy liczbę dróg przechodzącą tylko przez 1 punkt
if(x[0] > x[1] || (x[0] == x[1] && y[0] > y[1])) // sortujemy punkty najpierw po współrzędnej x, a potem y
z = x[0], x[0] = x[1], x[1] = z,
z = y[0], y[0] = y[1], y[1] = z;
if(x[1] > x[2] || (x[1] == x[2] && y[1] > y[2])) // c.d. sortowania
z = x[2], x[2] = x[1], x[1] = z,
z = y[2], y[2] = y[1], y[1] = z;
if(x[0] > x[1] || (x[0] == x[1] && y[0] > y[1])) // końcówka sortowania
z = x[0], x[0] = x[1], x[1] = z,
z = y[0], y[0] = y[1], y[1] = z;
if(y[0] <= y[1]) // odejmujemy liczbę dróg przechodzącą przez P1 i P2
ans = (ans-ways(x[0]-1, y[0]-1)*ways(x[1]-x[0], y[1]-y[0])%MOD*ways(n-x[1], m-y[1]))%MOD;
if(y[1] <= y[2]) // ... przez P2 i P3
ans = (ans-ways(x[1]-1, y[1]-1)*ways(x[2]-x[1], y[2]-y[1])%MOD*ways(n-x[2], m-y[2]))%MOD;
if(y[0] <= y[2]) // ... przez P1 i P3
ans = (ans-ways(x[0]-1, y[0]-1)*ways(x[2]-x[0], y[2]-y[0])%MOD*ways(n-x[2], m-y[2]))%MOD;
if(y[0] <= y[1] && y[1] <= y[2]) // dodajemy liczbę dróg przechodzącą przez wszystkie punkty
ans = (ans+ways(x[0]-1, y[0]-1)*ways(x[1]-x[0], y[1]-y[0])%MOD*ways(x[2]-x[1], y[2]-y[1])%MOD*ways(n-x[2], m-y[2]))%MOD;
print(ans);
}
}
Brak komentarzy:
Prześlij komentarz