CF1628C题解

FiraCode · 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,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;
}