AT_agc057_c [AGC057C] Increment or Xor

[problemUrl]: https://atcoder.jp/contests/agc057/tasks/agc057_c 正整数 $ N $ および、$ 2^N $ 項からなる数列 $ A\ =\ (A_0,\ A_1,\ \ldots,\ A_{2^N-1}) $ が与えられます。ここで各 $ A_i $ は $ 0 $ 以上 $ 2^N-1 $ 以下の整数であり、$ i\neq\ j $ ならば $ A_i\neq\ A_j $ が成り立ちます。 あなたは数列 $ A $ に対して、次の $ 2 $ 種類の操作を行うことができます： - 操作 $ + $：すべての $ i $ に対して、$ A_i $ を $ (A_i\ +\ 1)\ \bmod\ 2^N $ に変更する。 - 操作 $ \oplus $：$ 0 $ 以上 $ 2^N-1 $ 以下の整数 $ x $ を選ぶ。すべての $ i $ に対して $ A_i $ を $ A_i\oplus\ x $ に変更する。 ただしここで、$ \oplus $ はビット単位 $ \mathrm{XOR} $ 演算を表します。 ビット単位 $ \mathrm{XOR} $ 演算とは 非負整数 $ A,\ B $ のビット単位 $ \mathrm{XOR} $ 、$ A\ \oplus\ B $ は、以下のように定義されます。 - $ A\ \oplus\ B $ を二進表記した際の $ 2^k $ ($ k\ \geq\ 0 $) の位の数は、$ A,\ B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $、そうでなければ $ 0 $ である。 例えば、$ 3\ \oplus\ 5\ =\ 6 $ となります (二進表記すると: $ 011\ \oplus\ 101\ =\ 110 $)。 あなたの目的は、すべての $ i $ に対して $ A_i\ =\ i $ が成り立つようにすることです。目的を達成することが可能であるかを判定してください。本問題の制約下では、目的を達成することが可能な場合には、操作回数を $ 10^6 $ 回以下にできることが証明できます。そのような操作列を出力してください。

N/A

N/A

### 制約 - $ 1\leq\ N\leq\ 18 $ - $ 0\leq\ A_i\ \leq\ 2^N\ -\ 1 $ - $ i\neq\ j $ ならば $ A_i\neq\ A_j $ ### Sample Explanation 1 出力の操作列によって、数列 $ A $ は次のように変化します。 - 初期状態：$ A\ =\ (5,0,3,6,1,4,7,2) $ - 操作 $ + $：$ A\ =\ (6,1,4,7,2,5,0,3) $ - 操作 $ \oplus $ ($ x\ =\ 6 $)：$ A\ =\ (0,7,2,1,4,3,6,5) $ - 操作 $ + $：$ A\ =\ (1,0,3,2,5,4,7,6) $ - 操作 $ \oplus $ ($ x\ =\ 1 $)：$ A\ =\ (0,1,2,3,4,5,6,7) $ ### Sample Explanation 2 どのように操作を行っても、目的を達成することはできません。 ### Sample Explanation 3 $ 0 $ 回の操作により目的が達成できます。なお、空行の出力の有無は、ジャッジ結果に影響しません。