AtCoder Grand Contest 035：C - Skolem XOR Tree

問題
解法
解答

問題

https://atcoder.jp/contests/agc035/tasks/agc035_c

解法

N = 2^k であるときは No．なぜならば，N - (2 * N) のパス間で k bit 目が 1 であるものはないため，xor を N にすることは不可能だから．そうでないときは全て Yes となる．入出力例にある N = 3 のときのものに 4 - 5, 5 - (N + 1), (N + 1) - (4 + N), (4 + N) - (5 + N) と頂点と辺を足していく．これによって N が奇数である場合で解けた．N が偶数である場合は，(a ^ 1 ^ b) == N となる a, b の組を見つける必要がある．例えば，a = N - 1 とすると b = ((N - 1) ^ 1 ^ N) + N と定まる．O(N)．