2011-2012 Waterloo Local Contest, 24 September, 2011 E : Harmonious Matrices

問題概要

ある二次元ボードが調和的であるとは自分を含む5近傍の和がmod 2で0となるときにいう。H*W(H,W<40)の調和的な行列を出力する問題。ただし自明解としてすべて0というのがあるので、非自明解が存在するならば必ず非自明解を出力する。

解法

mod 2での連立1次方程式を解けばよい。このままだとMAX_W^6でTLEするがビット演算を使って高速化すれば通る。埋め込みはファイルが大きくなりすぎるので適切な圧縮が必要。

acceptされたコード

#include <cstdio>
#include <cstring>
using namespace std;

typedef unsigned long long bits;

const int MAX_W = 40;
const int dy[] = {1, -1, 0, 0, 0}, dx[] = {0, 0, -1, 1, 0};

int H, W;
bool fixed[MAX_W*MAX_W];
int one[MAX_W*MAX_W];
bits mat[MAX_W*MAX_W][(MAX_W*MAX_W + 1)/64 + 1];
bits tmp[(MAX_W*MAX_W + 1)/64 + 1];

void init(){
	scanf("%d%d", &H, &W);
}

void solve(){
	//build matrix
	memset(mat, 0, sizeof(mat));
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			for(int k=0; k<5; k++){
				int ny = i + dy[k], nx = j + dx[k];
				if(0<=ny && ny<H && 0<=nx && nx<W){
					int a = ny*W+nx;
					mat[i*W+j][a>>6] |= (1LL<<(a&63));
				}
			}
		}
	}

	//calc
	memset(fixed, false, sizeof(fixed));
	memset(one, 0, sizeof(one));
	const int S = H * W;
	const int L = (S + 1) / 64 + 1;
	for(int i=0; i<S; i++){
		int pivot = -1;
		for(int j=0; j<S; j++)if(!fixed[j] && ((mat[j][i>>6]>>(i&63))&1) ){
			pivot = j;
		}
		if(pivot == -1){
			for(int j=0; j<S; j++){
				if((mat[j][i>>6]>>(i&63))&1){
					mat[j][i>>6] &= ~(1LL<<(i&63));
					mat[j][S>>6] ^= 1LL<<(S&63);
				}
			}
			one[i] = 1;
			continue;
		}
		fixed[i] = true;

		memcpy(tmp, mat[pivot], sizeof(tmp));
		memcpy(mat[pivot], mat[i], sizeof(tmp));
		memcpy(mat[i], tmp, sizeof(tmp));

		for(int j=0; j<S; j++)if(i!=j && ((mat[j][i>>6]>>(i&63))&1)){
			for(int k=i>>6; k<L; k++){
				mat[j][k] ^= mat[i][k];
			}
		}
	}

	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			printf("%d%c", (int)(one[i*W+j] | ((mat[i*W+j][(S>>6)]>>(S&63))&1)), j==W-1?'\n':' ');
		}
	}
}

int main(){
	int T;
	scanf("%d", &T);
	for(int i=0; i<T; i++){
		init();
		solve();
	}
	return 0;
}