Edit

【pythonでABC171を解説】E - Red Scarf

問題概要

問題ページ

E - Red Scarf
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()

-Edit
-