EducationalCF48 D - Vasya And The Matrix

問題

n行m列の行列がある
i行目[j列目]の要素全てのxorが各i,jで与えられる
これに矛盾しない行列が存在するか判定し、存在するなら1個示す

解法

↓みたいにすればa[n-1], b[m-1]以外は全て矛盾しない
f:id:creep040:20180804112614j:plain
n-1行m-1列の数字をXとおくと、Xは
X = a[n-1] ^ (b[0] ^ b[1] ^ ... ^ b[m-2])
= b[m-1] ^ (a[0] ^ a[1] ^ ... ^ a[n-2])
と2通りで表せる
式変形すると
a[n-1] ^ (b[0] ^ b[1] ^ ... ^ b[m-2]) = b[m-1] ^ (a[0] ^ a[1] ^ ... ^ a[n-2])
→ a[0] ^ a[1] ^ ... ^ a[n-1] = b[0] ^ b[1] ^ ... ^ b[m-1]
これが成り立っていればさっき言ったような行列を出力、成り立たなければNO

int n, m, a[111], b[111], xa, xb, c[111][111];

signed main() {
	cin >> n >> m;
	rep(i,n) {
		cin >> a[i];
		xa ^= a[i];
	}
	rep(i,m) {
		cin >> b[i];
		xb ^= b[i];
	}
	if (xa!=xb) return cout << "NO" << endl, 0;
	
	rep(i,n-1) c[i][m-1] = a[i];
	rep(i,m-1) c[n-1][i] = b[i];
	c[n-1][m-1] = b[m-1]^xa^a[n-1];
	cout << "YES" << endl;
	rep(i,n) rep(j,m) cout << c[i][j] << (j==m-1 ? '\n' : ' ');
}