EducationalCF48 D - Vasya And The Matrix
問題
n行m列の行列がある
i行目[j列目]の要素全てのxorが各i,jで与えられる
これに矛盾しない行列が存在するか判定し、存在するなら1個示す
解法
↓みたいにすればa[n-1], b[m-1]以外は全て矛盾しない
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' : ' '); }