[1] binary trie による整数の表現

\(2^N\) 未満のすべての整数を、\(1\) の位から順に見ることで binary trie の葉として表すことにします。つまり、

• \(1\) の位，\(2^1\) の位，\(2^2\) の位，\(\ldots\)

の順に分類して、各整数を完全二分木の葉として表すことにします。

中間ノードは、\(\pmod{2}, \pmod{4}, \ldots\) で適当な値であるような整数全体に対応します。

---

[2] binary trie と操作 \(+\)

操作 \(+\) を行うと、整数 \(x\) の \(2\) 進法表記は次のように変化します。

• \(1\) の位は必ず変化する
• \(x\equiv 1\pmod{2}\) ならば、\(2^1\) の位が変化する
• \(x\equiv 3\pmod{4}\) ならば、\(2^2\) の位が変化する
• \(x\equiv 7\pmod{8}\) ならば、\(2^3\) の位が変化する
• \(\vdots\)

これは、binary trie の根から始めて \(1\) 方向に進みながら、パス上の中間ノードの \(0\) 方向・\(1\) 方向の子を入れ替えるという操作に対応します。

---

[3] binary trie と操作 \(\oplus\)

操作 \(\oplus\) を行うと、いくつかの桁について、すべての整数の \(2\) 進法表記が変化します。これは、binary trie において、いくつかの深さのノードの中間ノードの \(0\) 方向・\(1\) 方向の子を入れ替えるという操作に対応します。

---

[4] 本問の解法

結局、binary trie について行える操作は次の \(2\) 種です：

• 操作 (A)：いくつかの深さの中間ノードの子をすべて入れ替える
• 操作 (B)：葉を選び、根から葉までのパス上にある中間ノードの子をすべて入れ替える

後者の操作は、操作 \(\oplus\) によって選んだ葉が \(1\) を辿って到達できるようにしてから操作 \(+\) を行うことにより実現できます。

さらに、最も深い中間ノードに対する操作 (A) は行わないとしてよいです（すべての最も深い中間ノードに対して操作 (B) を行うことと等価になります）。この仮定のもと、どのパスに対して操作 (B) を行うべきかが確定します。必要な操作 (B) をすべて行ってしまえば、あとは一回の操作 (A) によって目的の状態を得られるかを考えればよく、これは容易です。

以上をまとめると、本問は例えば次の時間計算量・操作回数で解くことができることが分かります。

• 時間計算量：\(O(N2^N)\)
• 操作回数：\(2^N\) 以下

なお、必要に応じて最も深い中間ノードに対する操作 (A) も行うことで、操作回数 \(2^{N-1}\) 以下を達成することも可能です。