yukicoder : No.184 たのしい排他的論理和(HARD)

しょうもないWA/REを繰り返した。
http://yukicoder.me/problems/481

問題

N個の整数A[i]が与えられる。
これらのうち任意の数xorを取って得られる値は何通りあるか。

解法

A[i]をbitベクトルと考える。
あとは掃出し法などの要領でこれらA[i]の独立なベクトルの数pを求めて2^pを答えればよい。

int N;
ll A[100501];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	int ret=0;
	FOR(i,N) if(A[i]) {
		ret++;
		x=0;
		while((1LL<<(x+1))<=A[i]) x++;
		for(y=i+1;y<N;y++) if(A[y] & (1LL<<x)) A[y] ^= A[i];
	}
	cout<<(1LL<<ret)<<endl;
}

まとめ

掃出し法ミスったりA[i]の配列数ミスったり散々。