Polish version    English version  
  Historia OI -> VII OI 1999/2000 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Zasady organizacji
Wskazówki
Terminarz
Statystyki
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
VII Olimpiada Informatyczna 1999/2000

Zadanie: AUT
Autor: Grzegorz Jakacki
Automorfizmy

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:

  • dla dowolnych dwóch różnych wierzchołków u i v istnieje dokładnie jedna krawędź pomiędzy tymi wierzchołkami (tzn. albo u -> v, albo v -> u),
  • nie istnieją pętle (tzn. dla dowolnego wierzchołka u nie ma krawędzi u-> u ).

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.

Przykład

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:

[RYSUNEK]

Zadanie

Napisz program, który:

  • z pliku tekstowego AUT.IN wczyta opis permutacji n-elementowego zbioru wierzchołków,
  • obliczy liczbę t różnych n-wierzchołkowych turniejów, dla których ta permutacja jest automorfizmem,
  • zapisze w pliku tekstowym AUT.OUT resztę z dzielenia t przez 1000

Wejście

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)).

Wyjście

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.

Przykład

Dla pliku wejściowego AUT.IN

4
2
4
3
1

poprawną odpowiedzią jest plik wyjściowy AUT.OUT

4



Wersja do druku