Codeforces #940 : Div2 D. A BIT of an Inequality

Dまでは簡単だった。
https://codeforces.com/contest/1957/problem/D

問題

N要素の整数列Aが与えられる。
f(L,R)を、A[L....R]のxorとする。
1≦x≦y≦z≦Nとなるx,y,zのうち、f(x,y) xor f(y,z) ＞ f(x,z)となるものは何通りか。

解法

左辺はA[y]だけ2回xorが取られる点に注意。
A[y]のMSBがd bit目とすると、f(x,z)のd bit目が0だったら良いので、A[0]...A[y-1]とA[y+1]...A[z]で累積xorのd bit目が0/1のケースを数え上げておけば、x,zの候補の数がわかる。

int T,N;
int A[101010],H[101010];
int S[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>A[i];
			FOR(j,30) if(A[i]&(1<<j)) H[i]=j;
		}
		ll ret=0;
		
		FOR(j,30) {
			int cur=0;
			FOR(i,N) {
				if(A[i]&(1<<j)) cur^=1;
				S[i+1]=S[i]+cur;
			}
			cur=0;
			FOR(i,N) {
				if(A[i]&(1<<j)) cur^=1;
				if(H[i]==j) {
					ll A[2][2]={};
					A[1][cur^1]=S[N]-S[i];
					A[1][cur]=(N-i)-A[1][cur^1];
					A[0][cur]=S[i];
					A[0][cur^1]=i+1-S[i];
					
					ret+=A[0][0]*A[1][1]+A[0][1]*A[1][0];
				}
				
			}
		}
		cout<<ret<<endl;
	}
}

まとめ

この後はいまいち。Eまでは解いておきたかったな。