VII Olimpiada Informatyczna 1999/2000
|
Zadanie: AUT
|
Autor: Grzegorz Jakacki
|
Zawody II stopnia, dzień pierwszy | 9 lutego 2000 |
Plik źródłowy: | AUT.??? (np. pas, c, cpp) |
Plik wykonywalny: | AUT.exe |
Plik wejściowy: | AUT.in |
Plik wyjściowy: | AUT.out |
Turniejem nazywamy graf skierowany, w którym:
Oznaczmy przez p dowolną permutację zbioru wierzchołków turnieju. (Permutacją skończonego zbioru X nazywamy każdą różnowartościową funkcję z X w X.) Permutację p nazywamy automorfizmem, jeżeli dla dowolnych dwóch różnych wierzchołków u i v zwrot krawędzi pomiędzy u i v jest taki sam, jak pomiędzy p(u) i p(v) (tzn. u -> v jest krawędzią w turnieju wtedy i tylko wtedy, gdy p(u) -> p(v) jest krawędzią w tym turnieju). Dla zadanej permutacji p interesuje nas, dla ilu turniejów jest ona automorfizmem.
Weźmy zbiór wierzchołków oznaczonych liczbami 1,...,4 oraz permutację p:
p(1) = 2 |
p(2) = 4 |
p(3) = 3 | p(4) = 1. |
Istnieją tylko cztery turnieje, dla których ta permutacja jest automorfizmem:
Napisz program, który:
W pierwszym wierszu pliku tekstowego AUT.IN znajduje się jedna liczba naturalna n, 1<=n<= 10000, będąca liczbą wierzchołków. W kolejnych n wierszach znajduje się opis permutacji p. Zakładamy, że wierzchołki są ponumerowane liczbami od 1 do n. W wierszu (k+1)-szym znajduje się wartość permutacji p dla wierzchołka nr k (tzn. wartość p(k)).
W pierwszym i jedynym wierszu pliku tekstowego AUT.OUT powinna znaleźć się jedna liczba całkowita będąca resztą z dzielenia przez 1000 liczby różnych n-wierzchołkowych turniejów, dla których permutacja p jest automorfizmem.
Dla pliku wejściowego AUT.IN
4 2 4 3 1
poprawną odpowiedzią jest plik wyjściowy AUT.OUT
4