AtCoder Beginner Contest 126：F - XOR Matching

問題
解法
解答

問題

https://atcoder.jp/contests/abc126/tasks/abc126_f

解法

M = 0 のとき，答えは自明に (0, 0)．

M = 1 のとき，K = 0 のときしか答えは存在しない．

それ以外のとき，K < 2^M ならば答えが存在する．なぜならば，K >= 2^M のときには 0 ~ (2^M - 1) の数で xor をとっても 2^M になりえないから．答えは (K 以外の 0 ~ (2^M - 1) を降順に並べたもの), K, (K 以外の 0 ~ (2^M - 1) を昇順に並べたもの), K となる．2 つの K の間に含まれる (K 以外の 0 ~ (2^M - 1) を昇順に並べたもの) の xor は 0 ~ (2^M - 1) すべての xor が 0 であることより，K になる．また，2 つの K 以外の数の間に含まれる数は K 以外 2 回含まれるので xor は K になる（同じ数で 2 回 xor を取れば 0 になるので）．O(2^M)．