백준 2830번 행성 X3

백준 2830번: 행성 X3

아이디어

입력받은 모든 정수중 a번 비트에 1이 몇개 있는지 기록한다. 최대 100만이니까 0번 비트 ~ 19번 비트까지 기록하면 됨. 이제 각 비트별로 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);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    vector<int> bcnt(20); // 각 자리수별로 1이 몇 개 있는지

    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            if (v[j]&(1<<i)) bcnt[i]++;
        }
    }

    ll ans = 0;

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

    cout << ans;

    return 0;
}

여담

수학 넘 어렵다.