問題一覧 >
教育的問題
No.2184 A○B問題
レベル :
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ :
/
解いたユーザー数 105
作問者 : 👑
p-adic
/ テスター :
箱星
問題文最終更新日: 2023-01-13 11:02:37
問題文
入力に 5 次の置換 A,B が与えられます。
合成置換 A∘B を求めてください。
以下、置換とその 1 行記法について知らない人向けの説明を行います。(クリックで開く)
正整数 n に対し、n 次の置換とは大雑把には n 以下の正整数をシャッフルする関数のことです。より正確には以下のように定義されます:
定義(置換)
n 以下の正整数全体の集合を In と置く。n 次の置換とは、 In から In への全単射な写像である。
例えば In の恒等写像は n 次の置換であり、恒等置換と呼ばれます。
n 次の置換 a と b が与えられた時、その写像としての合成 a∘b もまた n 次の置換となり、それを a と b の合成置換と呼びます。つまり合成置換 a∘b は、n 以下の各正整数 i を a(b(i)) に送る写像として定まる n 次の置換です。
n 次の置換を表示するには様々な方法があり、例えば正整数 i の行き先を i が小さい順に列挙する記法を 1 行記法と呼びます。
1 行記法は流儀によっては列挙した数値全体をカッコで囲んだり列挙した数値をコンマで区切ったりしますが、ここではカッコで囲まず空白で区切ることにします。
例えば n=5 の時を考えましょう。5 以下の各正整数 i を 2i≡j(mod5)を満たす 5 以下の一意な正整数 j に送る写像 a は 5 次の置換であり、
a(1)a(2)a(3)a(4)a(5)=====24135
であるので 1 行記法では a が
2 4 1 3 5
と表記されます。より一般に、5 次の置換 a は 1 行記法で
a(1) a(2) a(3) a(4) a(5)
と表記されることになります。
入力
入力は以下の形式で標準入力から 2 行で与えられます:
- 1 行目に A が 1 行記法で与えられます。
- 2 行目に B が 1 行記法で与えられます。
ただし入力において 1 行記法の数値間の区切りには半角空白を使うことにします。
制約
入力は以下の制約を満たします:
- A は 5 次の置換
- B は 5 次の置換
出力
A∘B を 1 行記法で表した文字列を 1 行に出力してください。
ただし入力と同様に 1 行記法の数値間の区切りには半角空白を用いてください。
最後に改行してください。
サンプル
サンプル1
入力
1 2 3 4 5
2 4 5 1 3
出力
2 4 5 1 3
A は恒等置換なので、A∘B=B が成り立ちます。この等式を 1 行記法で表すと
1 2 3 4 5∘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
B は恒等置換なので、A∘B=A が成り立ちます。この等式を 1 行記法で表すと
3 1 5 4 2∘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
A と B は共に 1 と 2 を入れ替えるだけの 5 次の置換です。これらの合成置換は 1 と 2 を 2 回ひっくり返すだけなので恒等変換となります。すなわち
2 1 3 4 5∘2 1 3 4 5=1 2 3 4 5
となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。