問題一覧 > 教育的問題

No.2089 置換の符号

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 106
作問者 : 👑 p-adicp-adic / テスター : taiga0629kyoprotaiga0629kyopro
0 ProblemId : 8448 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-30 21:03:37

問題文

入力に $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$ が存在するということです:

  1. $i \neq j$ である。
  2. $a(i) = j$ である。
  3. $a(j) = i$ である。
  4. $n$ 以下の任意の正整数 $k$ に対し、$k \neq i$ かつ $k \neq j$ ならば、$a(k) = k$ である。

$a$ の符号は $\textrm{sgn}(a)$ と書かれる整数で、それは以下のように定義されます:

  1. $a$ が偶数個の互換の合成で表せるならば、$\textrm{sgn}(a) = 1$ である。
  2. $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もしくは右上の雲マークをクリックしてアカウントを作成してください。