XOR 합 3

백준 13710번: XOR 합 3

아이디어

앞에 올린 두가지 문제를 응용하면 된다.
v[l-1]^v[r] = a[l]^a[l+1]^..a[r-1]^a[r]이라는 사실과
비트별로 쪼개서 n번째 비트에 1이 몇 개 있는지 구하고 1의 개수 × 0의 개수 하면 값을 알 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> v(n+1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        v[i] = v[i-1]^x;
    }

    vector<int> bcnt(30); // 각 자리수별로 1이 몇 개 있는지
    for (int i = 0; i < 30; i++) {
        for (int j = 0; j <= n; j++) {
            if (v[j]&(1<<i)) bcnt[i]++;
        }
    }

    ll ans = 0;
    for (int i = 0; i < 30; i++) {
        ans += (1LL<<i)*bcnt[i]*(n+1-bcnt[i]);
    }
    
    cout << ans;

    return 0;
}

여담

XOR 고수의 길..
x^x=0이라는 사실을 알고있으면 큰 도움이 된다.