Codeforces #767 : Div1 C. Grid Xor

こちらもコードは短め。
https://codeforces.com/contest/1628/problem/C

問題

N*Nの行列Aがある。
Aの各要素を、隣接要素のxorで置き換えた行列Bが与えられる。
Aの全要素のxorを答えよ。

解法

Bを市松模様状に2回xorで累積和を取ると、全体のxorがAと同じ値になる行列を得られる。

int T,N;
int A[1010][1010];
ll B[1010][1010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&N);
		FOR(y,N) FOR(x,N) scanf("%d",&A[y][x]);
		
		ll ret=0;
		FOR(i,2) {
			FOR(y,N+3) FOR(x,N+3) B[y][x]=0;
			FOR(y,N) {
				FOR(x,N) {
					if((x+y)%2==i) {
						B[y+1][x+1]=A[y][x];
					}
					else {
						if(y==0) B[y+1][x+1]=0;
						else {
							B[y+1][x+1]=B[y][x]^B[y][x+1]^B[y][x+2]^B[y-1][x+1];
							ret^=B[y+1][x+1];
						}
					}
				}
			}
		}
		cout<<ret<<endl;
		
	}
}

まとめ

本番割とあっさりこれ思いつけてるな。