Processing math: 100%

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
-