考え方自体は典型的ではある
問題概要
個の整数
が与えられる。
これらから 2 個選んで XOR をとって得られる整数 ( 個ある) の総和を 1000000007 で割ったあまりを求めよ。
制約
考えたこと
XOR をみたら、とにかく「各桁ごとに考える」というのが定石ではある。その視点でいうと、問題は次のように考えることができる。
桁目について、
個の値のうち、
桁目が 1 であるものの個数を
とする
- このとき、答えには
を加算する
という風になる。
d 桁目が 1 である個数を求める
問題は「 個の値のうち、
桁目が 1 であるものの個数
」を求めることに帰着された。
XOR は「0 と 0 は 0」「1 と 1 は 0」「0 と 1 は 1」ということから、
のうち、
桁目が
であるものの個数を
のうち、
桁目が
であるものの個数を
としたとき、 個となる。
まとめ
まとめると、
- 各
桁目について
個の整数のうち、
桁目が 1 である個数は
、0 である個数を
として
を加算する
という風にして求めることができる。計算量は 。
#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; }