HourRank19 : B. What Are the Odds?

うーん、CでO(N^2)相当の解法を頑張りすぎてタイムロス。
https://www.hackerrank.com/contests/hourrank-19/challenges/what-are-the-odds

問題

N個の山からなるNimを考える。個々の山の石の数をS[i]とする。
なお、初手では特別な手として、山の区間[B,E]を指定し、それらの山の石をすべてなくすことができる。

先手が勝利するような初手の区間は何通りあるか。

解法

S[0..(B-1)]およびS[(E+1)..(N-1)]のすべてのxorを取った値が0になるならば、先手の勝ちである。
よってそのようなB,Eを求めよう。

まずBを定めると、X=xor(S[0..(B-1)])が求められる。
幸いSは最大でも10^5なので、Xも2^17未満である。
よってxor(A[(E+1)..(N-1)])をEをずらしながら求め、(E≧Bの範囲で)それぞれの登場回数をカウントし、Xと一致するものを数え上げればよい。

int N;
int S[505050];
int X[505050];
int num[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i];
		X[i+1]=X[i]^S[i];
	}
	
	ll ret=0;
	int R=0;
	for(i=N-1;i>=0;i--) {
		num[R]++;
		ret += num[X[i]];
		R^=S[i];
	}
	cout<<ret<<endl;
}

まとめ

これはすんなり。