考え方自体は典型的ではある

問題概要

$N$ 個の整数 $A_{1}, \dots, A_{N}$ が与えられる。
これらから 2 個選んで XOR をとって得られる整数 ( $\frac{N(N-1)}{2}$ 個ある) の総和を 1000000007 で割ったあまりを求めよ。

制約

$2 \le N \le 3 \times 10^{5}$
$0 \le A_{i} \lt 2^{60}$

考えたこと

XOR をみたら、とにかく「各桁ごとに考える」というのが定石ではある。その視点でいうと、問題は次のように考えることができる。

$d$ 桁目について、
$\frac{N(N-1)}{2}$ 個の値のうち、 $d$ 桁目が 1 であるものの個数を $a_{d}$ とする
このとき、答えには $a_{d} \times 2^{d}$ を加算する

という風になる。

d 桁目が 1 である個数を求める

問題は「 $\frac{N(N-1)}{2}$ 個の値のうち、 $d$ 桁目が 1 であるものの個数 $a_{d}$ 」を求めることに帰着された。

XOR は「0 と 0 は 0」「1 と 1 は 0」「0 と 1 は 1」ということから、

$A_{1}, \dots, A_{N}$ のうち、 $d$ 桁目が $1$ であるものの個数を $p$
$A_{1}, \dots, A_{N}$ のうち、 $d$ 桁目が $0$ であるものの個数を $q$

としたとき、 $pq$ 個となる。

まとめ

まとめると、

各 $d$ 桁目について
$N$ 個の整数のうち、 $d$ 桁目が 1 である個数は $p$ 、0 である個数を $q$ として
$pq \times 2^{d}$ を加算する

という風にして求めることができる。計算量は $O(N\log{A})$ 。

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

const int MOD = 1000000007;
int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    long long res = 0;
    long long two_factor = 1;
    for (int d = 0; d < 60; ++d) {
        long long even = 0, odd = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] & (1LL<<d)) ++odd;
            else ++even;
        }
        long long add = (odd * even) % MOD * two_factor % MOD;
        res = (res + add) % MOD;
        two_factor = (two_factor * 2) % MOD;
    }
    cout << res << endl;
}