No.2089 Sign of a Permutation
タグ : / 解いたユーザー数 115
作問者 : 👑
taiga0629kyopro
Problem Statement
You are given as input an integer $N$ greater than or equal to $2$ and a permutation $A$ of degree $N$.
Find the sign of $A$.
Below is an explanation for those unfamiliar with permutations and their signs. (Click to expand)
For a positive integer $n$, a permutation of degree $n$ is, roughly speaking, a function that shuffles the positive integers less than or equal to $n$. More precisely, it is defined as follows:
Definition (Permutation)
Let $I_n$ be the set of all positive integers less than or equal to $n$. A permutation of degree $n$ is a bijective map from $I_n$ to $I_n$.
Let $n$ be an integer greater than or equal to $2$, and let $a$ be a permutation of degree $n$. Roughly speaking, $a$ being a transposition means that $a$ swaps exactly $2$ numbers. More precisely, it means that there exist positive integers $i$ and $j$ less than or equal to $n$ satisfying the following:
- $i \neq j$.
- $a(i) = j$.
- $a(j) = i$.
- For any positive integer $k$ less than or equal to $n$, if $k \neq i$ and $k \neq j$, then $a(k) = k$.
The sign of $a$ is an integer written $\textrm{sgn}(a)$, defined as follows:
- If $a$ can be expressed as a composition of an even number of transpositions, then $\textrm{sgn}(a) = 1$.
- If $a$ cannot be expressed as a composition of an even number of transpositions, then $\textrm{sgn}(a) = -1$.
Here, $0$ is an even number, and the composition of $0$ transpositions is defined as the identity permutation.
Input
The input is given from standard input in the following format:
$N$ $S$
Line $1$ contains $N$, and line $2$ contains the string $S$, which lists the image $A(i)$ of each positive integer $i$ less than or equal to $N$ under $A$, in increasing order of $i$, separated by half-width spaces.
In what follows, the $S$ obtained in this way is referred to as "the string representing $A$ in $1$-line notation".
Constraints
The input $N, S$ satisfies the following constraints:
- $N$ is a non-negative integer between $2$ and $10^4$, inclusive
- $S$ is a string representing a permutation of degree $N$ in $1$-line notation
Output
Output the sign of $A$ on $1$ line.
Print a newline at the end.
Sample
Sample 1
Input
2 1 2
Output
1
$A$ is the identity permutation $1 \ 2$. The identity permutation can be regarded as the composition of $0$ transpositions, and it is also the composition of $2$ copies of the transposition $2 \ 1$. In particular, $A$ can be expressed as a composition of an even number of transpositions.
Therefore, the sign of $A$ is $1$.
Sample 2
Input
2 2 1
Output
-1
$A$ is the transposition $2 \ 1$. The only transposition of degree $2$ is $A$ itself, and since $A \circ A$ is the identity permutation, any composition of an even number of copies of $A$ is the identity permutation. In particular, $A$, which is not the identity permutation, cannot be expressed as a composition of an even number of transpositions.
Therefore, the sign of $A$ is $-1$.
Sample 3
Input
3 3 1 2
Output
1
$A$ is the permutation $3 \ 1 \ 2$. The composition of the transpositions $3 \ 2 \ 1$ and $1 \ 3 \ 2$ in this order is
$\displaystyle 3 \ 2 \ 1 \circ 1 \ 3 \ 2 = 3 \ 1 \ 2 = A $
so, in particular, $A$ can be expressed as a composition of an even number of transpositions.
Therefore, the sign of $A$ is $1$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。