Automorfizmy
Limit pamięci: 32 MB
Turniejem nazywamy graf skierowany, w którym:
- dla dowolnych dwóch różnych wierzchołków i istnieje
dokładnie jedna krawędź pomiędzy tymi wierzchołkami
(tzn. albo , albo ),
- nie istnieją pętle (tzn. dla dowolnego wierzchołka
nie ma krawędzi ).
Oznaczmy przez
dowolną permutację zbioru wierzchołków turnieju.
(Permutacją skończonego zbioru
nazywamy każdą różnowartościową
funkcję z
w
.)
Permutację
nazywamy
automorfizmem,
jeżeli dla dowolnych dwóch różnych wierzchołków
i
zwrot krawędzi
pomiędzy
i
jest taki sam, jak pomiędzy
i
(tzn.
jest krawędzią w turnieju wtedy i tylko wtedy,
gdy
jest krawędzią w tym turnieju).
Dla zadanej permutacji
interesuje nas, dla ilu turniejów jest ona
automorfizmem.
Przykład
Weźmy zbiór wierzchołków oznaczonych liczbami
oraz permutację :
, , , .
Istnieją tylko cztery turnieje, dla których ta permutacja
jest automorfizmem:
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis permutacji
-elementowego zbioru wierzchołków,
- obliczy liczbę różnych -wierzchołkowych turniejów,
dla których ta permutacja jest automorfizmem,
- wypisze na standardowe wyjście
resztę z dzielenia przez .
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba
naturalna , , będąca liczbą wierzchołków.
W kolejnych wierszach znajduje się opis permutacji . Zakładamy,
że wierzchołki są ponumerowane liczbami od 1 do . W wierszu
-szym znajduje się wartość permutacji dla wierzchołka
nr (tzn. wartość ).
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia
powinna znaleźć się jedna liczba całkowita będąca
resztą z dzielenia przez
liczby różnych -wierzchołkowych turniejów, dla których
permutacja jest automorfizmem.
Przykład
Dla danych wejściowych:
4
2
4
3
1
poprawną odpowiedzią jest:
4
Autor zadania: Grzegorz Jakacki.