CSAcademy Round #14 : D. Subarrays Xor Sum

かなり手間取った。
https://csacademy.com/contest/round-14/#task/subarrays-xor-sum

問題

N要素の整数列X[i]がある。
ここから、連続するA～B要素からなる部分列を全通り抜き出したとき、各要素のxor sumの総和を求めよ。

解法

B要素以下の部分列における総和から、(A-1)要素以下の部分列の総和を引く、と考えるとこの問題は結局あるx要素以下の部分列の総和を求める問題に置き換えられる。
各要素を2進数表記したとき、各ビットにおけるx要素以下の部分列の総和を考えよう。
これは尺取り法の要領で、各X[j]に対しX[j-a]～X[j]の1の登場回数の偶奇の和を0≦a＜xの範囲で考えればよい。

int N,A,B;
int X[101010];
int Y[101010];
int S[101010];
ll mo=1000000007;

ll hoge(int C) {
	if(C==0) return 0;
	ll tot=0;
	int d,i;
	FOR(d,30) {
		ll ret=0;
		ZERO(S);
		
		int num[2]={};
		FOR(i,N) {
			S[i+1]=S[i]+((X[i]>>d)&1);
			
			num[0]++;
			if((X[i]>>d)&1) swap(num[0],num[1]);
			if(i>=C) num[(S[i+1]-S[i+1-(C+1)])%2]--;
			ret += num[1];
		}
		tot += ((ret%mo)<<d)%mo;
	}
	return tot%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	FOR(i,N) cin>>X[i];
	cout<<(hoge(B)+mo-hoge(A-1))%mo<<endl;
}

まとめ

こういう問題いつも添え字を1ずらしたりしてデバッグに手間取る。