Codeforces #238 Div1 A. Unusual Product

CF238に参加。
Aに時間かかりすぎた上にしょうもないミスで落とすなど、グダグダすぎる落ち。
ほんとひどかった…。
http://codeforces.com/contest/406/problem/A

問題

0,1の2値のみを取るNxNの正方行列Aが与えられる。
この行列に対する変則内積を、i行目のベクトルとi列目のベクトルの内積を取ったものを、各iについて足しこんだものとする。
また、加算はGF(2)上で行われる。

この条件のもと、以下のクエリを処理せよ。

• iが与えられるので、Aのi行目の全要素を0と1反転する。
• iが与えられるので、Aのi列目の全要素を0と1反転する。
• Aの変則内積を出力する。

解法

この変則内積は各x,y(1≦x,y≦N)におけるA[y][x]*A[x][y]の総和である。
ここでx!=yの場合、A[y][x]*A[x][y]の値はx,yを逆にした場合と合わせ2回変則内積に足しこまれる。
よって、GF(2)の元では、要素の反転を問わずA[y][x]*A[x][y]の結果は変則内積に寄与しない。

結局変則内積に影響するのは、対角成分の和のみである。
結局どのクエリにおいてもどこかの対角成分の1つが0と1反転することになるが、その結果変則内積も0と1反転する。
よって実は行・列の反転クエリにおいては変則内積の値も合わせて反転するだけで良く、Aの中身を管理する必要はない。

int N;
int A[1002][1002];
int Q;

void solve() {
	int f,i,j,k,l,x,y;
	int ct=0;
	cin>>N;
	FOR(y,N) FOR(x,N) cin>>A[y][x];
	
	FOR(y,N) ct+=A[y][y];
	ct%=2;
	cin>>Q;
	while(Q--) {
		cin>>i;
		if(i==1 || i==2) {
			cin>>i;
			ct^=1;
		}
		else _P("%d",ct);
	}
	_P("\n");
}

まとめ

実は対角成分以外はどうでもよい、っていうのに気づくまで本番30分以上かかってしまった…。