Codeforces #473 Div2 F. Mahmoud and Ehab and yet another xor task

ちょっと戸惑ってしまった。
http://codeforces.com/contest/959/problem/F

問題

整数列Aが与えられる。
以下の各クエリについて答えよ。
クエリは整数L,Xからなる。Aの先頭L要素の部分集合のうち、xorを取った値がXとなるのはいくつあるか。

解法

クエリをLの大きさで並べ替えよう。

整数列が初期状態で空とし、１つずつ要素が増えていくことを考える。
個数がL個となった段階で、対応するクエリを処理しよう。

整数列の部分集合におけるxorの数え上げの定番テクとして、各整数をbit vectorとみなしその基底ベクトルを求めるテクがある。
これを応用し、Aの要素を追加するたびに、その要素が新しい基底ベクトルを構成するかしないかを数え上げよう。

L個の整数からp個の基底ベクトルを構築できたとする。
このp個の基底ベクトルの組み合わせでXが構築できるなら解は2^(L-p)、できないなら0である。

int N,Q;
int A[101010];
int L[101010],X[101010];
vector<int> PQ[101010];
ll ret[101010];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	FOR(i,Q) {
		cin>>L[i]>>X[i];
		L[i]--;
		PQ[L[i]].push_back(i);
	}
	vector<pair<int,int>> mask;
	ll zero=1;
	FOR(i,N) {
		x=A[i];
		FORR(m,mask) if(x&m.second) x^=m.first;
		if(x==0) zero=zero*2%mo;
		else {
			y=0;
			for(j=0;j<20;j++) if(x&(1<<j)) y=1<<j;
			FORR(m,mask) if(m.first&y) m.first^=x;
			mask.push_back({x,y});
		}
		
		FORR(p,PQ[i]) {
			int v=X[p];
			FORR(m,mask) if(v&m.second) v^=m.first;
			if(v==0) ret[p]=zero;
			
		}
		
	}
	FOR(i,Q) cout<<ret[i]<<endl;
	
}

まとめ

解に0か2の累乗しか出ない点で気が付きそう。