Wyspa do zasiedlenia

Tutaj możesz uzyskać pomoc w rozwiązywaniu zadań dostępnych w ramach AlgoLigi

Wyspa do zasiedlenia

Postautor: witman » 21 paź 2013, 22:52

Potrzebna wiedza: iloczyn wektorowy, algorytm Euklidesa, Wzór Picka, szybkie potęgowanie modularne, małe twierdzenie Fermata (lub arytmetyka dużych liczb).

Przyjmijmy najpierw:
k - liczba obszarów wykluczonych z zasiedlenia
m - wyznaczona liczba miast na wyspie,
z - liczba zawodów
a1,a2..az - liczby przedstawicieli poszczególnych zawodów
sk - całkowita (suma z ai) liczba kolonistów.
MP = 1000000007 (liczba pierwsza)

W pierwszej kolejności, na podstawie podanych wspólrzędnych, należy obliczyć pole wyspy (P) (wykorzystujemy iloczyn wektorowy) oraz liczbę punktów brzegowych (B) (wykorzystując algorytm Euklidesa). To samo robimy dla obszarów niedostępnych. Następnie korzystamy z przekształconego wzoru Picka do obliczenia liczby miast m = P -B/2 +(1-k).

Mając obliczoną liczbę miast, pozostaje obliczyć wynik = m^sk (mod MP). Na nieszczeście sk nie jest podane bezpośrednio. Można więc wyjść z wzoru: m^a1*m^a2*...*m^az, wykonując oczywiście wszystkie obliczenia modulo MP i szybkie potęgowanie modularne.
Niestety dla z=200000, przy limicie 1s, to (przynajmniej jak na klaster wybrany do tego zadania) o wiele za dużo obliczeń. Trzeba więc wyznaczyć wynik wykonując jedno potęgowanie jako:
m^(sk=a1+a2+...+az). Tu pojawia się kolejna trudność, bo, z uwagi na zakres liczb a1..az, sumowanie grozi przekroczeniem zakresu nawet long long int. Ten problem można rozwiązać na dwa sposoby:
1. (trudniej) Arytmetyka dużych liczb - takie rozwiązanie zastosował Mariusz podczas konkursu.
2. (łatwiej) Małe twierdzenie Fermata - z którego wynika, że to sumowanie kolonistów możemy wykonywać modulo (MP-1).
Jak by nie liczyć, wynik=m^sk.

Uwaga. Jeśli w programie nie wyróżni się przypadku gdy m>0 i sk=0 (wtedy wynik=1), to trzeba też uważać na szczególny przypadek, gdy m jest wielokrotnością MP, a sk jest (niezerową) wielokrotnością (MP-1). Wtedy m=0(mod MP) i sk=0(mod (MP-1)). Licząc m^sk typowym algorytmem szybkiego potęgowania, dostaniemy wynik=1, a właściwy to 0.
witman
Koordynator AlgoLigi
 
Posty: 78
Rejestracja: 10 kwie 2013, 21:03

Wróć do Zadania

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 1 gość

cron