問題一覧 > 教育的問題

No.2184 A○B問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 105
作問者 : 👑 p-adicp-adic / テスター : 箱星箱星
0 ProblemId : 8440 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-01-13 11:02:37

問題文

入力に 55 次の置換 A,BA,B が与えられます。

 

合成置換 ABA \circ B を求めてください。

 

以下、置換とその 11 行記法について知らない人向けの説明を行います。(クリックで開く)

 

正整数 nn に対し、nn 次の置換とは大雑把には nn 以下の正整数をシャッフルする関数のことです。より正確には以下のように定義されます:

 

定義(置換)

nn 以下の正整数全体の集合を InI_n と置く。nn 次の置換とは、 InI_n から InI_n への全単射な写像である。

 

例えば InI_n の恒等写像は nn 次の置換であり、恒等置換と呼ばれます。

 

nn 次の置換 aabb が与えられた時、その写像としての合成 aba \circ b もまた nn 次の置換となり、それを aabb の合成置換と呼びます。つまり合成置換 aba \circ b は、nn 以下の各正整数 iia(b(i))a(b(i)) に送る写像として定まる nn 次の置換です。

 

nn 次の置換を表示するには様々な方法があり、例えば正整数 ii の行き先を ii が小さい順に列挙する記法を 11 行記法と呼びます。

11 行記法は流儀によっては列挙した数値全体をカッコで囲んだり列挙した数値をコンマで区切ったりしますが、ここではカッコで囲まず空白で区切ることにします。

例えば n=5n = 5 の時を考えましょう。55 以下の各正整数 ii2ij(mod5)2i \equiv j \pmod{5}を満たす 55 以下の一意な正整数 jj に送る写像 aa55 次の置換であり、

a(1)=2a(2)=4a(3)=1a(4)=3a(5)=5\displaystyle \begin{array}{rcl} \displaystyle a(1) &\displaystyle = &\displaystyle 2 \\ \displaystyle a(2) &\displaystyle = &\displaystyle 4 \\ \displaystyle a(3) &\displaystyle = &\displaystyle 1 \\ \displaystyle a(4) &\displaystyle = &\displaystyle 3 \\ \displaystyle a(5) &\displaystyle = &\displaystyle 5 \end{array}

であるので 11 行記法では aa

2 4 1 3 5\displaystyle 2 \ 4 \ 1 \ 3 \ 5

と表記されます。より一般に、55 次の置換 aa11 行記法で

a(1) a(2) a(3) a(4) a(5)\displaystyle a(1) \ a(2) \ a(3) \ a(4) \ a(5)

と表記されることになります。

入力

入力は以下の形式で標準入力から 22 行で与えられます:

  • 11 行目に AA11 行記法で与えられます。
  • 22 行目に BB11 行記法で与えられます。

ただし入力において 11 行記法の数値間の区切りには半角空白を使うことにします。

制約

入力は以下の制約を満たします:

  • AA55 次の置換
  • BB55 次の置換

出力

ABA \circ B11 行記法で表した文字列を 11 行に出力してください。

ただし入力と同様に 11 行記法の数値間の区切りには半角空白を用いてください。

最後に改行してください。

サンプル

サンプル1
入力
1 2 3 4 5
2 4 5 1 3
出力
2 4 5 1 3

AA は恒等置換なので、AB=BA \circ B = B が成り立ちます。この等式を 11 行記法で表すと

1 2 3 4 52 4 5 1 3=2 4 5 1 3\displaystyle 1 \ 2 \ 3 \ 4 \ 5 \circ 2 \ 4 \ 5 \ 1 \ 3 = 2 \ 4 \ 5 \ 1 \ 3

となります。

サンプル2
入力
3 1 5 4 2
1 2 3 4 5
出力
3 1 5 4 2

BB は恒等置換なので、AB=AA \circ B = A が成り立ちます。この等式を 11 行記法で表すと

3 1 5 4 21 2 3 4 5=3 1 5 4 2\displaystyle 3 \ 1 \ 5 \ 4 \ 2 \circ 1 \ 2 \ 3 \ 4 \ 5 = 3 \ 1 \ 5 \ 4 \ 2

となります。

サンプル3
入力
2 1 3 4 5
2 1 3 4 5
出力
1 2 3 4 5

AABB は共に 1122 を入れ替えるだけの 55 次の置換です。これらの合成置換は 112222 回ひっくり返すだけなので恒等変換となります。すなわち

2 1 3 4 52 1 3 4 5=1 2 3 4 5\displaystyle 2 \ 1 \ 3 \ 4 \ 5 \circ 2 \ 1 \ 3 \ 4 \ 5 = 1 \ 2 \ 3 \ 4 \ 5

となります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。