Time Limit: 2 sec / Memory Limit: 2048 MB
配点 : 100 点
カッコウ「対称群のかけ算表が与えられるので順列に対応させてください」
カッコウ「添え字が小さくて読み書きしにくいので括弧を使わせてください」
問題文
N を正整数とする.(1, 2, \ldots, N) の順列全体を \mathfrak{S}_N と書く.f \in \mathfrak{S}_N は列 (f(1), f(2), \ldots, f(N)) と同一視する.f, g \in \mathfrak{S}_N に対し,f \circ g \in \mathfrak{S}_N を,k = 1, 2, \ldots, N に対し (f \circ g)(k) = f(g(k)) として定める.また,\mathfrak{S}_N のすべての元を辞書順に並べたものを P(1) < P(2) < \cdots < P(N!) とする.
(N!)^2 個の整数 A(i, j) (1 \le i, j \le N!) が与えられる.(1, 2, \ldots, N!) の順列 q = (q(1), q(2), \ldots, q(N!)) であって,すべての 1 \le i, j \le N! に対し P(q(i)) \circ P(q(j)) = P(q(A(i, j))) を満たすものをすべて求め,辞書順に出力せよ.
なお,条件を満たす q が存在することが制約によって保証されている.
制約
- 1 \le N \le 6.
- 1 \le A(i, j) \le N! (1 \le i, j \le N!).
- 問題文の条件を満たす q が存在する.
部分点
- N = 1, 2, 3, 4, 5, 6 を満たすデータセットに正解した場合は,それぞれ 1, 2, 4, 8, 16, 69 点が与えられる.
入力
入力は以下の形式で標準入力から与えられる.
N A(1, 1) A(1, 2) \cdots A(1, N!) A(2, 1) A(2, 2) \cdots A(2, N!) \vdots A(N!, 1) A(N!, 2) \cdots A(N!, N!)
出力
1 行目に,条件を満たす q の個数を出力せよ.
以降,条件を満たす q を辞書順に 1 行ずつ,それぞれ q(1), q(2), \ldots, q(N!) をこの順に空白区切りで出力せよ.
入力例 1
3 6 4 5 2 3 1 5 6 4 3 1 2 4 5 6 1 2 3 3 1 2 5 6 4 2 3 1 6 4 5 1 2 3 4 5 6
出力例 1
6 2 3 6 5 4 1 2 6 3 4 5 1 3 2 6 4 5 1 3 6 2 5 4 1 6 2 3 5 4 1 6 3 2 4 5 1
\mathfrak{S}_3 の元は以下の 6 個である:
- P(1) = (1, 2, 3)
- P(2) = (1, 3, 2)
- P(3) = (2, 1, 3)
- P(4) = (2, 3, 1)
- P(5) = (3, 1, 2)
- P(6) = (3, 2, 1)
例えば q = (3, 2, 6, 4, 5, 1) のとき,
- P(q(1)) = (2, 1, 3)
- P(q(2)) = (1, 3, 2)
- P(q(3)) = (3, 2, 1)
- P(q(4)) = (2, 3, 1)
- P(q(5)) = (3, 1, 2)
- P(q(6)) = (1, 2, 3)
となる. P(q(2)) \circ P(q(3)) = P(q(4)) = P(q(A(2, 3))) などが成り立つことが確認できる.