[AtCoder] ABC 147 D – Xor Sum 4

2019年12月10日2019年12月17日

問題

方針

各ビットごとに着目

整数 \( A, B\) を \( 2 \) 進数表記で下位から \( i\) ビット目を \( a_i, \ b_i \) と表します。例えば、\( A = a_1a_2a_3 \) , \( B = b_1b_2b_3 \) としたとき、

\[ A \oplus B = a_1 \oplus b_1 + 2 \times a_2 \oplus b_2 + 2^2 \times a_3 \oplus b_3\]

と計算できます。ここで、整数 \( A_i \) の \( j \ (0 \leq j \leq 60) \) 番目のビットを \( a(i, j) \) として、次の計算を考えます。

\[
\begin{eqnarray}
\sum_{i = 2}^{N} A_1 \oplus A_i &=& \sum_{i = 1}^{N} \sum_{j=0}^{60} 2^{j} \times a(0, j) \oplus a(i, j)\\
&=& \sum_{j=0}^{60} 2^{j} \sum_{i = 1}^{N} a(0, j) \oplus a(i, j)
\end{eqnarray}
\]

上記の計算において、

\[ \sum_{i = 1}^{n} a(0, j) \oplus a(i, j)\]

は、\( N \) 個の整数において \( j \) 番目のビットが何個立っているかを知っていれば計算できるので、その累積和をあらかじめ計算しておきます。

コード

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

ll b[300005][61]{};
ll c[300005][61]{};

int main() {
    int N;
    cin >> N;
    ll A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int l = 61;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < l; j++) {
            ll t = (1ll<<j);
            if ((t & A[i]) != 0) {
               b[i][j] = 1; 
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < l; j++) {
            c[i + 1][j] = c[i][j] + b[i][j];
        }
    }
    
    ll ans = 0;
    ll mod = pow(10, 9) + 7;
    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < l; j++) {
            ll t = 1ll<<j;
            ll k;
            if ((t & A[i]) != 0) {
                k = N - (i + 1) - (c[N][j] - c[i + 1][j]);
            } else {
                k = (c[N][j] - c[i + 1][j]);
            }
            t %= mod;
            ans += k * t;
            ans %= mod;
        }
    }
    
    cout << ans << "\n";
    return 0;
}