Xây dựng mảng $C[n][n] = a[n][n] \oplus b[n][n]$ $\rightarrow$ cần flip các bit 1 về 0
Với $r[i]$ là flip toàn bộ hàng $i$, $c[j]$ là flip toàn bộ cột $j$, để $a[i][j]$ thành $b[i][j]$ thì $a[i][j] \oplus r[i] \oplus c[j] = b[i][j]$
$$\rightarrow r[i] \oplus c[j] = C[i][j]$$
Như vậy cần tìm mảng r, c thoả mãn với mọi i, j đều có $r[i] \oplus c[j] = C[i][j]$
xét
$r[i] \oplus c[j] = C[i][j]$
$r[0] \oplus c[0] = C[0][0]$
$r[i] \oplus c[0] = C[i][0]$
$r[0] \oplus c[j] = C[0][j]$
$VT = C[0][0] \oplus C[i][0] \oplus C[0][j] \oplus C[i][j]$
$ \leftrightarrow r[i] \oplus c[j] \oplus r[0] \oplus c[0] \oplus r[i] \oplus c[0] \oplus r[0] \oplus c[j] = VP$
$ \leftrightarrow r[i] \oplus r[i] \oplus c[j] \oplus c[j] \oplus r[0] \oplus r[0] \oplus c[0] \oplus c[0] = VP$
$ \leftrightarrow 0 = C[0][0] \oplus C[0][j] \oplus C[i][0] \oplus C[i][j] $
Như vậy với mỗi $i, j (i > 0 || j > 0)$ thì ta chỉ cần xét $C[0][0] \oplus C[0][j] \oplus C[i][0] \oplus C[i][j] == 0$, nếu không thì in ra $-1$
Tiếp theo ta xét 2 trường hợp $r[0] = 0$ và $r[0] = 1$ vì hệ phương trình có dạng $r[i] \oplus c[j] = C[i][j]$
Đây là hpt tuyến tính trên trường $GF(2)$, có chính xác 2 nghiệm khi hệ nhất quán: nghiệm với $r[0] = 0$ và nghiệm với $r[0] = 1$.
CM: Xét $(r,c)$ là một nghiệm ($res = r + c$) thì $(r \oplus a, c \oplus a)$ cũng là nghiệm với a thuộc $\{0,1\}$ vì:
$$(r[i] \oplus a) \oplus (c[j] \oplus a) = r[i] \oplus c[j] \oplus ( a \oplus a ) = r[i]\oplus c[j] = C[i][j]$$
dễ thấy $a \oplus a = 0$ nên việc $\oplus a$ vào mọi $r[i]$ và $c[j]$ sẽ ko thay đổi pt $\rightarrow a$ chỉ có thể là 0 hoặc 1, hpt có đúng 2 nghiệm với $ a = 0 : (r,c)$ và $a = 1 : (r \oplus 1, c \oplus 1)$
TH1: $r[0] = 0$
với $i = 0$, ta có
$r[0] \oplus c[j] = C[0][j]$
$\leftrightarrow 0 \oplus c[j] = C[0][j]$
$\leftrightarrow c[j] = C[0][j]$
với $i > 0$ ta có
$\rightarrow r[i] \oplus c[0] = C[i][0]$
mà $c[0] = C[0][0]$, do đó
$r[i] = C[i][0] \oplus c[0] = C[i][0] \oplus C[0][0]$
Chứng minh tương tự cho TH2, ta có
$r[i] = C[i][0] \oplus c[0] = C[i][0] \oplus (C[0][0] \oplus 1) = C[i][0] \oplus C[0][0] \oplus 1$
```c++
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#pragma iloveganyu
bool a[500][500];
signed main(){
int n;
cin >> n;
for (int i = 0; i < n; i++){
string s;
cin >> s;
for (int j = 0; j < n; j++){
char x = s[j];
a[i][j] = (x == '1');
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
char x;
cin >> x;
a[i][j] = a[i][j] ^ (x == '1');
if (i > 0 or j > 0){
if (a[i][j] xor a[i][0] xor a[0][j] xor a[0][0]){
cout << -1;
return 0;
}
}
}
}
int p1 = 0;
for (int i = 0; i < n; i++){
p1 += a[0][i];
//cerr << a[0][i] << " ";
if (i > 0){
p1 += a[i][0] xor a[0][0];
}
}
int p2 = 1;
for (int i = 0; i <n ; i ++){
p2 += a[0][i] xor 1;
if (i > 0) p2 += a[i][0] xor (a[0][0] xor 1);
}
cout << min(p1, p2) << nl;
}
```
suika
Created at
6 likes