题解：CF1628C Grid Xor

Jim_Franklin · 2025-01-07 18:54:09 · 题解

是 zak 的做法 QwQ。

我们钦定 b 的第一行都是 0。

然后根据 a_{i,j}=b_{i-1,j}\oplus b_{i+1,j}\oplus b_{i,j+1}\oplus b_{i,j-1} （不存在的 b 我们将他设为 0 ）就可以递推出 b 数组，现在要证明此时的 b 数组一定是合法的。

题目中提到了 b 一定是有解的（这个其实可以构造证明）。

设 v=b_{1,1} 将 b_{1,1} 异或上 v 这时会影响到的位置有 (2,1) 和 (1,2) 发现能够同时影响到他们的格子还有 (2,2) 于是把 b_{2,2} 再异或上 v 重复这么做下去，并对第一行的其他格子如法炮制，就能把第一行的 b 全部变成 0。

于是我们证明了对于任意一个合法的 b 我们一定可以将他转换为一个第一行都是 0 的且合法的 b' 。

于是我们的做法就得到了证明。

void sol(){
    n=rd();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)a[i][j]=rd();
    int ans=0;
    for(int i=1;i<n;i++)
        for(int j=1;j<=n;j++)
            res[i+1][j]=a[i][j]^res[i-1][j]^res[i][j+1]^res[i][j-1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
          ans^=res[i][j],res[i][j]=0;
    cout<<ans<<'\n';
}