0 人解决，3 人已尝试。
0 份提交通过，共有 4 份提交。
9.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
A tournament is a directed graph in which:
for each two different vertices u and v there exsits exactly one edge between them (i.e. either u -> v or v -> u),
there are no loops (i.e. for each vertex u there is no edge u-> u ).
Let p denote any permutation of the set of tournament’s vertices. (A permutation of a finite set is an injective function from X to X.) The permutation p is called an automorphism, if for each two different vertices u and v the direction of the edge between u and v is the same as the direction of the edge between p(u) and p(v) (i.e. u -> v is an edge in the tournament if and only if p(u) -> p(v) is an edge in this tournament). For a given permutation p, we want to know for how many tournaments this permutation is an automorphism.
Example
Let’s take the set of vertices 1,…,4 and the permutation p:
p(1) = 2
p(2) = 4
p(3) = 3
p(4) = 1.
There are only four tournaments for which this permutation is an automorphism:
Task
Write a program which:
1.reads the description of a permutation of an n-element set,
2.computes t, the number of different n-element tournaments for which this permutation is an automorphism,
3.writes the remainder of dividing t by 1000
In the first line of there is one integer n, 1<=n<= 10000, which is the number of vertices. In the following n lines there is a description of a permutation p. We assume that vertices are numbered from 1 to n. In line (k+1) there is a value of the permutation p for the vertex k (i.e. the value p(k)).
In the first and only line of there should be one integer equal to the remainder of dividing t (the number of different n-vertex tournaments for which p is an automorphism) by 1000.
4 2 4 3 1
4 hint:
0 人解决，3 人已尝试。
0 份提交通过，共有 4 份提交。
9.9 EMB 奖励。