Codeforces ECR #058 : G. (Zero XOR Subset)-less

これもどうにか解けて良かったね。
https://codeforces.com/contest/1101/problem/G

問題

整数列Aが与えられる。
これをいくつかの連続した部分列に分割したい。
その際、部分列のSubsetを取ったとき、Subsetの取り方に関わらず全体のxorが0にならないようにしたい。
最大何個の部分列に分割できるか。

解法

全体のxorが0の時は解なし。

貪欲法で選ぶ。
すでにA[0...(L-1)]の部分列が選ばれており、各部分列のxorの値の集合Cが選ばれているものとする。
A[L...(N-1)]をさらに分割していくわけだが、次の分割列A[L..R]をできるだけ短くするようにしたい。
その場合、CにA[L..R]とA[(R+1)..(N-1)]を加えてもbitvectorが互いに独立を保つような最小のRを選択しよう。

int N;
int A[202020];
int S[202020];

template<class C> int gf2_rank(vector<C>& V) { /* input */
	int i,j;
	int N=V.size();
	FOR(i,N) {
		sort(V.begin()+i,V.end(),greater<C>());
		if(V[i]==0) break;
		C msb=1;
		while(msb<<1 <= V[i]) msb<<=1;
		FOR(j,N) if(j!=i) if(V[j]&msb) V[j]^=V[i];
	}
	return N-count(V.begin(),V.end(),0);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) {
		cin>>A[i];
		S[i]=S[i-1]^A[i];
	}
	
	if(S[N]==0) return _P("-1\n");
	
	vector<int> C;
	int L=0,R=0;
	while(L<N) {
		for(R=L+1;R<N;R++) {
			x=S[R]^S[L];
			y=S[N]^S[R];
			vector<int> C2=C;
			C2.push_back(x);
			C2.push_back(y);
			if(gf2_rank(C2)!=C2.size()) continue;
			C.push_back(x);
			gf2_rank(C);
			break;
			
		}
		L=R;
	}
	
	cout<<C.size()+1<<endl;
	
}

まとめ

結構計算重いかと思ったけど800msぐらいで終わるのね。