CSAcademy Round #10 : E. Xor Closure

なんか似たようなの見たことある。
https://csacademy.com/contest/round-10/#task/xor-closure

問題

N個の整数からなる集合Sがある。
Sにいくつか要素を加え、a,b∈Sであるa,bに対しa xor bがSに含まれるようにしたい。
最少何個要素を求めればよいか。

解法

なんかどこかで見たことある。
S中の要素をbit vectorとみなすと、S中の要素の独立なベクトルがd個だとするとSは2^d個の要素が最小。
よってSのrankを求め、2^(rank(S)) - Nを答えればよい。

int N;
ll A[101010];

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

まとめ

他で見たことなかったら解けなかったね。