Codeforces #270 Div1 F. Design Tutorial : Change the Goal

はいはい固有ベクトル固有ベクトル…と思ったらもうひとひねり必要だった。
http://codeforces.com/contest/472/problem/F

問題

N要素の数列X[i]、Y[i]が与えられる。
ある２つの数値i,jを選択してX[i] ^= X[j]を行う、ということを繰り返し、X[i]をY[i]に出来るか。
出来るならその手順を答えよ。

解法

xorについては以下の法則がある。

• i!=jなら、X[i]^=X[j]、X[j]^=X[i]、X[i]^=X[j]と３回処理を行いX[i]とX[j]を交換できる。
• i!=jなら、X[i]^=X[j]を２回行うと元に戻る。また、何度か処理を行っても逆順で同じ処理を行えばもとに戻る。

こういう問題の定番として、各数値を30桁の２進数表記から、30次元の0,1値を取るベクトルとみなし、固有ベクトルを求めることを考える。
前者より掃出し法により固有ベクトルを求めることができる。

例えば、X[i]から固有ベクトルA[i]、Y[i]から固有ベクトルB[i]を求められるとする。
あとはA[i]からB[i]が生成できれば、Y[i]から固有ベクトルB[i]を求める手順の逆順でB[i]からY[i]を生成できる。

int N;
int X[10001],Y[10001],RX,RY;

vector<pair<int,int> > OX,OY,XY;

void diag(int V[],int& r,vector<pair<int,int> >& VP) {
	int i,j,k;
	for(i=30;i>=0;i--) {
		for(j=r;j<N;j++) if(V[j]&(1<<i)) {
			if(j!=r) {
				VP.push_back(make_pair(j,r));
				VP.push_back(make_pair(r,j));
				VP.push_back(make_pair(j,r));
				swap(V[j],V[r]);
			}
			FOR(j,N) if(j!=r && (V[j]&(1<<i))) {
				VP.push_back(make_pair(j,r));
				V[j]^=V[r];
			}
			r++;
			break;
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i];
	FOR(i,N) cin>>Y[i];
	diag(X,RX,OX);
	diag(Y,RY,OY);
	if(RX<RY) return _P("-1\n");
	
	FOR(i,RX) if(X[i]) {
		int msb=1;
		while(msb*2<=X[i]) msb*=2;
		FOR(j,RX) if((Y[j]&msb) && i!=j) {
			XY.push_back(make_pair(j,i));
			X[j]^=X[i];
		}
		if(!(Y[i]&msb)) {
			XY.push_back(make_pair(i,i));
			X[i]=0;
		}
	}
	
	FOR(i,RX) if(X[i]!=Y[i]) return _P("-1\n");
	reverse(OY.begin(),OY.end());
	
	_P("%d\n",OX.size()+XY.size()+OY.size());
	ITR(it,OX) _P("%d %d\n",it->first+1,it->second+1);
	ITR(it,XY) _P("%d %d\n",it->first+1,it->second+1);
	ITR(it,OY) _P("%d %d\n",it->first+1,it->second+1);
}

まとめ

Y→Bを生成する手順を逆順で回してB→Yを生成する、というアイデアが面白かった。