CPSCO2019 Session3 : E - Enumerate Xor Sum

やっぱりさっきのGと同じ配点とは感じない。
https://atcoder.jp/contests/cpsco2019-s3/tasks

問題

N要素の整数列Aが与えられる。
k=1～Nについて順次以下の値を求めよ。

X=A[1] xor A[2] xor .... xor A[k]とする。
(A[1] xor X) + (A[2] xor X) + ... + (A[k] xor X)　を答えよ。

解法

bit毎に(A[i] xor X)が1になる個数を累積和の要領で求めよう。
各bitにおいて、A[i]のそのbitが0/1になる個数がわかれば、(A[1] xor X), (A[2] xor X), ... ,(A[k] xor X)において当該bitが1になる個数もわかる。

int N;
int C[31];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		ll ret=0;
		FOR(j,30) {
			if(x&(1<<j)) C[j]++;
			ll num=(C[j]%2==0)?(C[j]):(i+1-C[j]);
			ret+=num<<j;
		}
		cout<<ret<<endl;
	}
}

まとめ

これは典型っぽいね。