Codeforces #512 Div1 B. Vasya and Good Sequences

これは手間取ったけど通ってよかった。
http://codeforces.com/contest/1053/problem/B

問題

正整数列Aが与えられる。
Aの連続した部分列のうち、以下の条件を満たすものはいくつあるか。

• 各要素について、2進数表記したとき1の立つビットの位置を変えることができる。
• その時、部分列中の全要素のxorが0にできる。

解法

部分列が条件を満たすには以下の２点を満たせばよい。

• ２進数表記したとき、全要素における1の数が偶数
• 1つの要素が登場する1の数の過半数を超えることがない。

ここで、部分列の先頭位置A[L]を固定したとき、対応するA[R]が何通りあるかを求めることにしよう。
前者の対応は容易で、前処理として1の数の累積和を取ったうえで、奇数・偶数となる位置の数を数え上げておけばよい。
こうするとA[0...R]の1の数とA[0...(L-1)]の1の数の偶奇が一致するRを高速に求められる。

問題は後者。
ただ、各要素1の数は最小1、最大60である。
よって、Rは[L...(L+59)]の範囲では1要素が過半数となることがあるかもしれないが、それ以降は過半数になることはない。
なのでRの範囲は60個ほど総当たりするだけでよい。

以下は念のため120個まで見ているね。

int N;
ll A[303030];
int C[303030],SC[303030];
ll tot[303030][2];
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	tot[0][0]=1;
	
	for(i=1;i<=N;i++) {
		cin>>A[i];
		//A[i]=(1LL<<60)-1;
		C[i]=__builtin_popcountll(A[i]);
		SC[i]=SC[i-1]+C[i];
		
		tot[i][0]=tot[i-1][0];
		tot[i][1]=tot[i-1][1];
		tot[i][SC[i]%2]++;
		
		
		int sum=C[i];
		int ma=C[i];
		int cur=i;
		while(cur>0 && sum<=120) {
			if(ma*2<=sum && sum%2==0) ret++;
			cur--;
			sum+=C[cur];
			ma=max(ma,C[cur]);
		}
		if(cur>0) ret+=tot[cur-1][SC[i]%2];
	}
	
	
	cout<<ret<<endl;
	
}

まとめ

もうチョイすっきり書けばよかった。