yukicoder : No.803 Very Limited Xor Subset

これは思いついておきたかった。
https://yukicoder.me/problems/no/803

問題

N個の整数列A[i]が与えられる。
ここからいくつかを選択することを考える。
その際、以下の条件がM個与えられる。

• 範囲A[L...R]のうち、選択する要素は奇数/偶数でなければならない

条件を満たす選びかたのうち、選んだ値のxorを取った値がXとなるのは何通りか。

解法

koba氏のツイートがわかりやすかったです。

まず条件を無視して考える。
S[i] = A[i]を選択するなら1、しないなら0
とする。

A[i]およびXについて2進数表記した場合の各桁について、
xor(A[i]*S[i]) = X
出なければならないので、A,Xの上限が10^9以下であることを考えるとGF(2)における30個の式ができる。
さらに、与えられた条件もいくつかのS[i]の和(xor)が奇数または偶数であることを指定するものなので、１個の条件から１個の式ができる。

よって、これらの連立方程式の解の数を求めればよい。
これには係数行列と拡大係数行列のrankを求め、rankが不一致なら解なし、一致ならその組み合わせはpow(2,(N-rank))通りである。

int N,M,X;
int A[303];
const int MAT=402;
int mat1[402][402];
int mat2[402][402];
ll mo=1000000007;

int gf2_rank(int A[MAT][MAT],int n) { /* input */
	int i,j,k;
	FOR(i,n) {
		int be=i,mi=n+1;
		for(j=i;j<n;j++) {
			FOR(k,n) if(A[j][k]) break;
			if(k<mi) be=j,mi=k;
		}
		if(mi>=n) break;
		FOR(j,n) swap(A[i][j],A[be][j]);
		
		FOR(j,n) if(i!=j&&A[j][mi]) {
			FOR(k,n) A[j][k] ^= A[i][k];
		}
	}
	return i;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>X;
	FOR(i,N) cin>>A[i];
	FOR(i,30) {
		FOR(j,N) if(A[j]&(1<<i)) mat1[i][j]=mat2[i][j]=1;
		if(X&(1<<i)) mat2[i][N]=1;
	}
	FOR(i,M) {
		cin>>r>>x>>y;
		x--,y--;
		for(j=x;j<=y;j++) mat1[30+i][j]=mat2[30+i][j]=1;
		mat2[30+i][N]=r;
	}
	
	int r1=gf2_rank(mat1,402);
	int r2=gf2_rank(mat2,402);
	if(r1!=r2) return _P("0\n");
	ll ret=1;
	FOR(i,N-r1) ret=ret*2%mo;
	cout<<ret<<endl;
	
	
}

まとめ

２の累乗になるのは予想着いたんだけど、条件を方程式に組み込むところに至らなかったのが残念。