Решение задачи Художественное занятие с Codeforces

Камень... Бумага!

После того как Карен придумала детерменированную стратегию для победы (поражения?) в игру камень-ножницы-бумага, её брат, Коёми, придумал новую игру в качестве замены. Правила этой игры таковы.

В начале выбирается целое число n. Коёми и Карен независимо выбирают по n различных положительных целых чисел, которые обозначаются как x 1, x 2, ..., x n и y 1, y 2, ..., y n, соответственно. Затем они показывают друг другу свои последовательности и меняют их до тех пор, пока все 2n чисел не станут различными. Затем две последовательности фиксируются и больше не меняются.

После этого они считают число упорядоченных пар (i, j) (1 ≤ i, j ≤ n), таких, что величина x i xor y j равна одному из 2n целых чисел. Здесь xor означает побитовое сложение по модулю 2 двух целых чисел. Эта операция часто обозначается как ^ или xor в языках программирования.

Карен выигрывает, если число таких пар чётно, в противном случае выигрывает Коёми. Определите победителя.