C. Quaternary Matrix 详细题解

一、题目回顾

给定一个 $n \times m$ 的四进制矩阵（元素仅为 $0,1,2,3$），要求修改最少数量的元素，使得矩阵满足：

1. 每一行所有元素的按位异或和为 $0$
2. 每一列所有元素的按位异或和为 $0$

最后输出最小修改次数 + 任意一个合法矩阵。

---

二、核心前置知识

1. 异或性质

   • $x \oplus x = 0$
   • $x \oplus 0 = x$
   • 修改 $a[i][j] \oplus v$，会让第 $i$ 行异或和、第 $j$ 列异或和同时异或 $v$

2. 目标 让所有行异或和 $R_i=0$，所有列异或和 $C_j=0$。

---

三、完整标程代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,m,a[1009][1009];
char s[1009];
vector <ll> row[4],col[4];
inline ll read(){
	ll s = 0,w = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
	return s * w;
}
int main(){
	t = read();
	while (t --){
		n = read(),m = read();
		for (ll i = 1;i <= 3;i += 1) row[i].clear(),col[i].clear();
		for (ll i = 1;i <= n;i += 1){
			scanf("%s",s + 1);
			for (ll j = 1;j <= m;j += 1) a[i][j] = s[j] - '0';
		}
		for (ll i = 1;i <= n;i += 1){
			ll sum = 0;
			for (ll j = 1;j <= m;j += 1) sum ^= a[i][j];
			if (sum) row[sum].emplace_back(i);
		}
		for (ll j = 1;j <= m;j += 1){
			ll sum = 0;
			for (ll i = 1;i <= n;i += 1) sum ^= a[i][j];
			if (sum) col[sum].emplace_back(j);
		}
		ll ans = 0;
		for (ll i = 1;i <= 3;i += 1){
			while (row[i].size() && col[i].size()){
				ans += 1;
				a[row[i].back()][col[i].back()] ^= i;
				row[i].pop_back(),col[i].pop_back();
			}
		}
		for (ll i = 1;i <= 3;i += 1){
			ll j = i % 3 + 1,k = j % 3 + 1;
			while (row[i].size() && col[j].size() && col[k].size()){
				ans += 2;
				a[row[i].back()][col[j].back()] ^= j;
				a[row[i].back()][col[k].back()] ^= k;
				row[i].pop_back(),col[j].pop_back(),col[k].pop_back();
			}
			while (col[i].size() && row[j].size() && row[k].size()){
				ans += 2;
				a[row[j].back()][col[i].back()] ^= j;
				a[row[k].back()][col[i].back()] ^= k;
				col[i].pop_back(),row[j].pop_back(),row[k].pop_back();
			}
		}
		for (ll i = 1;i <= 3;i += 1) for (ll j = 1;j <= 3;j += 1) if (i != j){
			while (row[i].size() >= 2 && col[j].size() >= 2){
				ll r1 = row[i].back(); row[i].pop_back();
				ll r2 = row[i].back(); row[i].pop_back();
				ll c1 = col[j].back(); col[j].pop_back();
				ll c2 = col[j].back(); col[j].pop_back();
				ans += 3;
				a[r1][c1] ^= i;
				a[r2][c1] ^= (i ^ j);
				a[r2][c2] ^= j;
			}
		}
		for (ll i = 1;i <= 3;i += 1){
			while (row[i].size()) ans += 1,a[row[i].back()][1] ^= i,row[i].pop_back();
			while (col[i].size()) ans += 1,a[1][col[i].back()] ^= i,col[i].pop_back();
		}
		printf("%lld\n",ans);
		for (ll i = 1;i <= n;i += 1,puts("")) for (ll j = 1;j <= m;j += 1) printf("%lld",a[i][j]);
	}
	return 0;
}

---

四、标程逐段详细解析

1. 变量定义

• a[1009][1009]：存储矩阵
• row[v]：存储异或和为 $v$ 的所有行号
• col[v]：存储异或和为 $v$ 的所有列号
• ans：最小修改次数

---

2. 输入 + 初始化

清空行、列异常容器，读入矩阵并转为数字存储：

n = read(),m = read();
for (ll i=1;i<=3;i++) row[i].clear(),col[i].clear();
for (ll i=1;i<=n;i++){
    scanf("%s",s+1);
    for (ll j=1;j<=m;j++) a[i][j] = s[j]-'0';
}

---

3. 计算所有行、列的异或和

遍历每一行、每一列，计算异或和，非 0 的存入对应容器：

// 计算行异或和
for (ll i=1;i<=n;i++){
    ll sum=0;
    for (ll j=1;j<=m;j++) sum ^= a[i][j];
    if(sum) row[sum].push_back(i);
}
// 计算列异或和
for (ll j=1;j<=m;j++){
    ll sum=0;
    for (ll i=1;i<=n;i++) sum ^= a[i][j];
    if(sum) col[sum].push_back(j);
}

---

4. 阶段 1：最优修复（1 次修改解决 2 个异常）

规则：行偏差 $v$ + 列偏差 $v$ → 修改 $(r,c) \oplus v$ 代价：$+1$，最优方案

for (ll i=1;i<=3;i++){
    while(row[i].size() && col[i].size()){
        ans++;
        a[row[i].back()][col[i].back()] ^= i;
        row[i].pop_back();
        col[i].pop_back();
    }
}

---

5. 阶段 2：次优修复（2 次修改解决 3 个异常）

利用 $1\oplus2=3,\ 1\oplus3=2,\ 2\oplus3=1$：

• 1 个行偏差 + 2 个列偏差 → 同一行改两列
• 1 个列偏差 + 2 个行偏差 → 同一列改两行 代价：$+2$

ll j = i%3+1, k = j%3+1;
while(row[i] && col[j] && col[k]){
    ans+=2;
    a[r][c1]^=j; a[r][c2]^=k;
}

---

6. 阶段 3：标准修复（3 次修改解决 4 个异常）

处理 2 个行偏差 + 2 个列偏差，修改矩形三个角： 代价：$+3$

a[r1][c1] ^= i;
a[r2][c1] ^= i^j;
a[r2][c2] ^= j;

---

7. 阶段 4：兜底修复（最后清理）

所有剩余异常，直接修改第一行 / 第一列：

// 剩余行异常：修改该行第 1 列
while(row[i].size()) ans++, a[r][1]^=i;
// 剩余列异常：修改第 1 行该列
while(col[i].size()) ans++, a[1][c]^=i;

---

8. 输出答案 + 矩阵

printf("%lld\n",ans);
for(ll i=1;i<=n;i++){
    for(ll j=1;j<=m;j++) printf("%lld",a[i][j]);
    puts("");
}

---

五、算法正确性与最优性

1. 严格最小修改：按照 $1 \to 2 \to 3$ 次修改的顺序贪心修复，永远选当前代价最小的方案。
2. 合法性保证：最终所有行、列异或和均为 $0$。
3. 复杂度：$O(nm)$，完美满足题目 $\sum nm \le 10^6$ 限制。

---

六、总结

1. 核心操作：$a[i][j] \oplus v$ 同时修正行、列偏差
2. 修复策略：贪心优先低代价修改
3. 保证：最小次数 + 合法矩阵
4. 适用范围：$n,m \le 10^3$，四进制矩阵通用解法