AtCoder Grand Contest 035：A - XOR Circle

問題

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

解法

(a ^ b) == c は (a ^ b ^ c) == 0 と同値より，高々 3 種類の数字しか登場してはならない．3 種類の場合は (a ^ b ^ c) == 0 となる a, b, c がそれぞれ N / 3 個，2 種類の場合は 0 でない整数が N / 3 * 2 個と 0 が N / 3 個，1 種類場合は 0 が N 個あれば条件を満たすので，この 3 パターンのどれかに当てはまるかどうかを確かめればよい．O(NlogN)．

解答

https://atcoder.jp/contests/agc035/submissions/6377108