CPSCO2019 Session3 E - Enumerate Xor Sum (500)

E - Enumerate Xor Sum

概要

長さNの数列Aが与えられる。i=1, …, Nについて(A1 xor X) + (A2 xor X) + … (Ai xor X)を出力せよ。ただし、X = A1 xor A2 xor … xor Aiとする。

制約

1 ≦ N ≦ 3 * 10^5
0 ≦ Ai < 2^30

方針

2進けたごとにみていくとうまくいく。

各2進けたごとの(A1 xor X) + (A2 xor X) + … (Ai xor X)は次の通り。

• X = 0のときはA1, A2, … Aiの1の個数
• X = 1のときはA1, A2, … Aiの0の個数

これは各iごとに累積和で管理してゆく。出力は2進の各桁の値を使ってもとの10進数にもどせばよい。

解答

Submission #5412228 - CPSCO2019 Session3

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll N;
	cin >> N;
 
	vector<ll> A(N);
	rep(i, N) cin >> A[i];
 
	vector<ll> dig(30, 0);
	for(int i = 0; i < N; i++){
		ll ans = 0;
		for(int k = 0; k < 30; k++){
			dig[k] += (A[i] >> k) & 1;
			ans += (dig[k] % 2 == 1 ? i+1 - dig[k] : dig[k]) * (1 << k);
		}
 
		cout << ans << endl;
	}
}