No.2089 置換の符号
タグ : / 解いたユーザー数 109
作問者 : 👑
p-adic
/ テスター :
taiga0629kyopro
問題文
入力に $2$ 以上の整数 $N$ と $N$ 次の置換 $A$ が与えられます。
$A$ の符号を求めてください。
以下、置換やその符号について知らない人向けの説明します。（クリックで開く）
正整数 $n$ に対し、$n$ 次の置換とは大雑把には $n$ 以下の正整数をシャッフルする関数のことです。より正確には以下のように定義されます：
定義（置換）
$n$ 以下の正整数全体の集合を $I_n$ と置く。$n$ 次の置換とは、 $I_n$ から $I_n$ への全単射な写像である。
$n$ を $2$ 以上の整数とし、$a$ を $n$ 次の置換とします。$a$ が互換であるとは、大雑把には $a$ がちょうど $2$ つの数を入れ替えるということです。より正確には、以下を満たす $n$ 以下の正整数 $i$ と $j$ が存在するということです：
- $i \neq j$ である。
- $a(i) = j$ である。
- $a(j) = i$ である。
- $n$ 以下の任意の正整数 $k$ に対し、$k \neq i$ かつ $k \neq j$ ならば、$a(k) = k$ である。
$a$ の符号は $\textrm{sgn}(a)$ と書かれる整数で、それは以下のように定義されます：
- $a$ が偶数個の互換の合成で表せるならば、$\textrm{sgn}(a) = 1$ である。
- $a$ が偶数個の互換の合成で表せないならば、$\textrm{sgn}(a) = -1$ である。
ただし $0$ は偶数であり、互換 $0$ 個の合成は恒等置換として定義されます。
入力
入力は次の形式で標準入力から与えられます：
$N$ $S$
$1$ 行目に $N$ が与えられ、$2$ 行目に $N$ 以下の各正整数 $i$ の $A$ による行き先 $A(i)$ を $i$ が小さい順に半角空白区切りで並べた文字列 $S$ が与えられます。
また、以下このようにして得られる $S$ を「$A$ を $1$ 行記法で表記した文字列」と表現することにします。
制約
入力 $N, S$ は以下の制約を満たします：
- $N$ は $2$ 以上 $10^4$ 以下の非負整数
- $S$ は $N$ 次の置換を $1$ 行記法で表記した文字列
出力
$A$ の符号を $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 1 2
出力
1
$A$ は恒等置換 $1 \ 2$です。恒等置換は互換 $0$ 個の合成とみなすこともできますし、互換 $2 \ 1$ を $2$ 個合成したものでもあります。特に $A$ は互換偶数個の合成で表すことができます。
従って $A$ の符号は $1$ です。
サンプル2
入力
2 2 1
出力
-1
$A$ は互換 $2 \ 1$ です。$2$ 次の互換は $A$ 自身しか存在しませんが、$A \circ A$ が恒等置換であることから $A$ を偶数個合成したものは恒等置換となります。特に恒等置換でない $A$ は互換偶数個の合成で表すことができません。
従って $A$ の符号は $-1$ です。
サンプル3
入力
3 3 1 2
出力
1
$A$ は置換 $3 \ 1 \ 2$ です。互換 $3 \ 2 \ 1$ と $1 \ 3 \ 2$ のこの順での合成は
$\displaystyle 3 \ 2 \ 1 \circ 1 \ 3 \ 2 = 3 \ 1 \ 2 = A $
であるので、特に $A$ は互換偶数個の合成で表すことができます。
従って $A$ の符号は $1$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。