Soxy Log

競技プログラミングに関すること

AtCoder AGC 035 A - XOR Circle

問題


AtCoder AGC035 A - XOR Circle

解法


例えば、N=4の場合
a_1 \oplus a_3=a_2
a_2 \oplus a_4=a_3
a_3 \oplus a_1=a_4
a_4 \oplus a_2=a_1
が成立するとき、条件を満たす。
4つの式を掛け合わせて整理すると
(a_1 \oplus a_2 \oplus a_3 \oplus a_4) \oplus (a_1 \oplus a_2 \oplus a_3 \oplus a_4) = a_1 \oplus a_2 \oplus a_3 \oplus a_4
これを満たすのは、a_1 \oplus a_2 \oplus a_3 \oplus a_4=0の場合のみである。
このように、条件を満たすのはN個のa[i]のxorを掛け合わせた値が0の場合であることを利用する。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int N;
    cin >> N;
    vector<ll> a(N);
    for(int i(0);i<N;++i) cin >> a[i];
    ll xor_product(a[0]);
    for(int i(1);i<N;++i) xor_product = xor_product ^ a[i];
    if(xor_product == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}