yukicoder : No.2212 One XOR Matrix

これは割とすんなり。
https://yukicoder.me/problems/no/2212

問題

整数Nが与えられる。
(2^N)*(2^N)のグリッドに、0以上2^(2N)未満の整数を1つずつ入れる。
各行・各列のxorが1となるものを構築せよ。

解法

サンプルで4*4のグリッドで条件を満たすものが与えられる。

また、以下の4*4のグリッドは各列・行のxorが0となる。

 0  1  4  5
 2  3  6  7
 8  9 12 13
10 11 14 15

あとはグリッドを4*4の小グリッドに分割し、対角成分には前者、それ以外には後者を、16ずつ値をずらしながら埋めて行けばよい。

int N;
int A[4][4]={
{7,14,0,8},
{4,12,2,11},
{15,9,6,1},
{13,10,5,3},
};
int C[4][4]={
{0,1,4,5},
{2,3,6,7},
{8,9,12,13},
{10,11,14,15},
};
int B[1024][1024];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N;
	if(N==1) {
		cout<<-1<<endl;
		return;
	}
	int nex=0;
	FOR(y,1<<(N-2)) FOR(x,1<<(N-2)) {
		int y2,x2;
		FOR(y2,4) FOR(x2,4) {
			if(x==y) B[y*4+y2][x*4+x2]=nex+A[y2][x2];
			else B[y*4+y2][x*4+x2]=nex+C[y2][x2];
		}
		nex+=16;
		
	}
	FOR(y,1<<N) {
		FOR(x,1<<N) {
			cout<<B[y][x]<<" ";
		}
		cout<<endl;
	}
}

まとめ

さっと思いつけて良かったね。