CF1270I Xor on Figures 题解

· · 题解

联考搬的神仙题。

有一种 naive 的想法是把这个操作刻画成一个矩阵，然后用 bitset 跑异或高斯消元，答案是增广列中非零系数的个数。在联考中过了 k\le 7。

接下来就是人类智慧了。

我们定义矩阵乘法 A\times B=C。具体的，C_{i,j}=\oplus_{x,y}a_{x,y}b_{i-x,j-y}，注意这里的 i-x 和 j-y 均是在模意义下的。

据我测试得出，这个运算不满足结合律，这个在接下来会避免踩坑。

由于异或操作的自反性，我们将初始矩阵变成全零矩阵，就是全零矩阵变成初始矩阵。

记 A 为初始矩阵，B 为“操作矩阵”（具体地，在第 i 次操作中，把 B_{x_i,y_i} 设成 1 即可）。

那么我们要找到一个矩阵 C，满足：A=B\times C。答案就是矩阵 C 中非零系数的个数。

不难得出 C=A\times B^{-1}。我们只需要找到 B 的逆矩阵即可。

令单位矩阵为 I，那么有 I_{0,0}=1 而 I_{i,j}=0（显然 i\ne0 且 j\ne 0）。

我们发现对于矩阵 T，T^2 就是将 T 中 (x,y) 的点的值转移到 (2x,2y)（因为其它点位都会被异或抵消，而 (2x,2y) 不变）。

也就是说 T^{2^k} 就是一个单位矩阵！

那么我们要找的逆矩阵其实就是 T^{2^k-1}！

然后我们就只需要求 C=A\times B^{2^k-1} 即可。

好，还记得上面说的“跳坑”吗？

因为传统的矩阵快速幂是需要满足结合律的，这样才能先算 B^{2^k-1}，再算 A\times B^{2^k-1}。

但这个很好解决，我们将传统的矩阵快速幂中，初始矩阵（即单位矩阵）改成 A 即可。

本题轻微卡常，大概可以优化两个点：

代码和讲解稍有出入：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
const int mod=1e9+7;
const int INF=0x3f3f3f3f3f3f3f3f;
const int M=1<<9;//size of matrix
int mask;
struct matrix{
    int n,a[M][M];
    matrix(int _n){
        n=_n;
        memset(a,0,sizeof(a));
    }
    friend matrix operator * (matrix a,matrix b){
        int n=a.n;
        matrix c(n);
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                if(a.a[i][j])
                    for(int k=0;k<n;++k)
                        for(int l=0;l<n;++l)
                            c.a[(i+k)&mask][(j+l)&mask]^=a.a[i][j]*b.a[k][l];
        return c;
    }
};
int k,t;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("mc.in","r",stdin);
    // freopen("mc.out","w",stdout);
    cin>>k;
    int prek=k;
    k=(1<<k);
    mask=k-1;
    matrix A(k),T(k);
    for(int i=0;i<k;i++){
        for(int j=0;j<k;j++){
            cin>>A.a[i][j];
        }
    }
    cin>>t;
    for(int i=1;i<=t;i++){
        int x,y;
        cin>>x>>y;
        x--;y--;
        T.a[x][y]=1;
    }
    matrix ans=A;//这个运算不满足结合律，所以只能这么写
    for(int i=0;i<prek;i++){
        ans=T*ans;
        T=T*T;
    }
    int cnt=0;
    for(int i=0;i<k;i++)for(int j=0;j<k;j++)cnt+=(ans.a[i][j]!=0);
    cout<<cnt<<"\n";
    return 0;
}
/*

*/