問題概要
問題ページ
-
E - Red Scarf
問題ページへ移動する
問題文
猫のすぬけくんが \(N (\textbf{偶数})\) 匹います。各すぬけくんには \(1, 2, \ldots, N\) の番号が振られています。
各すぬけくんは首に赤いスカーフを巻いており、スカーフにはそのすぬけくんが一番好きな非負整数が \(1\) つ書き込まれています。
すぬけくんたちは最近、整数の xor(排他的論理和)と呼ばれる演算を覚えました。
xor とは
\(n\) 個の非負整数 \(x_1,x_2, \ldots, x_n\) について、それらの xor、 \(x_1~\textrm{xor}~x_2~\textrm{xor}~\ldots~\textrm{xor}~x_n\) は以下のように定義されます。
- \(x_1~\textrm{xor}~x_2~\textrm{xor}~\ldots~\textrm{xor}~x_n\) を二進表記した際の \(2^k(k \geq 0)\) の位の数は、\(x_1,x_2, \ldots, x_n\) のうち、二進表記した際の \(2^k(k \geq 0)\) の位の数が \(1\) となるものの個数が奇数ならば \(1\)、そうでなければ \(0\) となる。
例えば、\(3~\textrm{xor}~5 = 6\) となります。
早速この演算を使いたくなったすぬけくんたちは、自分以外のすぬけくんのスカーフに書かれた整数の xor を計算することにしました。
番号 \(i\) が振られたすぬけくんが計算した、自分以外のすぬけくんのスカーフに書かれた整数の xor が \(a_i\) であることが分かっています。
この情報を元に、各すぬけくんのスカーフに書かれた整数を特定してください。
制約
- 入力はすべて整数である
- \(2 \leq N \leq 200000\)
- \(N\) は\(\textbf{偶数}\)
- \(0 \leq a_i \leq 10^9\)
- 与えられた情報と整合するようなスカーフ上の整数の組合せが存在する
問題の考察
ACコード
import sys def solve(): input = sys.stdin.readline mod = 10 ** 9 + 7 n = int(input().rstrip('\n')) a = list(map(int, input().rstrip('\n').split())) bs = 0 for v in a: bs ^= v ls = [] for v in a: bs ^= v ls.append(bs) bs ^= v print(*ls) if __name__ == '__main__': solve()