本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-12 18:15:03

【题目链接】

题解思路：

若能找到一个 $(i , j)$ 集合，表示只取 $a_{i,j}$ 时，原矩阵的每个元素的贡献都足 $1$，那么答案就是 $a_{i , j}$ 的异或和，用 $c_{i , j}$ 来表示 $a_{i,j}$ 取不取，取为 $1$，不取为 $0$。

我们第一行随便赋值 $c_{1,i}$，我们统一赋值成 $1$ 然后从第二行开始从上往下扫描，对于当前位置 $(i , j)$，我们的目标是让 $a_{i - 1 , j}$ 的贡献为 $1$ 即：

$$c_{i - 2,j} \oplus c_{i - 1 , j - 1} \oplus c_{i - 1}{j + 1} \oplus c_{i , j} = 1$$

这样就得到了 $c_{i,j}$。

不过现在还要证明 $a_{n,i}$ 的贡献为 $1$。

考虑现在还有一个合法方案 $c_{i , j}$ $'$，我们逐一比较求得的 $c_{1 , j}$ 与 $c_{1,j}$ $'$，如果不一样，则修改 $c_{1 , i}$ $'$，然后一次修改受影响的 $c_{i , j}$ $'(i > 1)$，整个过程保证 $a_{i , j}$ $'$ 的贡献仍然为 $1$。可以发现后两行一定是修改 $(n - 1 , n - i) , (n - 1 , n - i + 2) , (n , n - i + 1)$，则最后一行 $a_{i,j}$ $'$ 的贡献不变

AC Code:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream> 
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N][N] , c[N][N];
void solve () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i)  
        for (int j = 1; j <= n; ++ j)
            cin >> a[i][j];
    for (int i = 1; i <= n; ++ i) c[1][i] = 1;\/\/先把c[1][i]初始化成1
    for (int i = 1; i <= n; ++ i) c[i][n + 1] = 0;
    for (int i = 2; i <= n; ++ i) 
        for (int j = 1; j <= n; ++ j) {
            c[i][j] = c[i - 2][j] ^ c[i - 1][j - 1] ^ c[i - 1][j + 1] ^ 1;
        }
    int ans = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            if (c[i][j])
                ans ^= a[i][j];
    cout << ans << endl;
}
int main() {
    int T;
    cin >> T;
    while (T --) solve();
    return 0;
}