[AtCoder] ABC 171 E – Red Scarf

2020年12月14日

問題

方針

排他的論理和 xor を \( \oplus \) で表現します。\( i \) 番目のスカーフの番号を \( b_i \) とすると、

\[ a_i = b_1 \oplus b_2 \oplus \cdots  \oplus b_{i-1} \oplus a_{i+1} \oplus \cdots \oplus b_{N}\]

ここで、\( a_i \) の排他的論理和を考えます。

\begin{eqnarray}
a_1 \oplus \cdots \oplus a_{N} &=& (b_1 \oplus \cdots \oplus b_1) \oplus \cdots \oplus(b_N \oplus \cdots \oplus b_N)\\
&=& b_1 \oplus \cdots \oplus b_N
\end{eqnarray}

となります。これは、\( b_i \oplus b_i = 0 \) と \( b_i \oplus 0 = b_i \) と \( N \) が偶数であることを利用して導けます。

また、

\begin{eqnarray}
a_1 \oplus \cdots \oplus a_{N}\oplus a_1 &=& b_1 \oplus \cdots \oplus b_N \oplus (b_2 \oplus \cdots \oplus b_N)\\
&=& b_1
\end{eqnarray}

となるので、任意の \( b_i \) について求めることができます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    ll a[N];
    ll t = 0;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        t = (t ^ a[i]);
    }
    for (int i = 0; i < N; i++) {
        if (i == N - 1) {
            cout << (t ^ a[i]) << "\n";
        } else {
            cout << (t ^ a[i]) << " ";
        }
    }
    return 0;
}