CF1270I Xor on Figures 题解

· · 题解

前言

第一次做这种重定义矩阵+求逆题记录一下，感觉这个题好多人类智慧。

正文

0x00 题目分析

观察题目中的操作可得几个性质。

  1. 首先一对 \left(p,q\right) 至多操作一次，否则操作次数将会变多。

  2. 操作具有交换律。

  3. 操作具有结合律（可以理解为在全 0 矩阵上操作，然后 xor 在一起，最终结果不变）。

  4. 操作具有自反性。

  5. 在上述条件下可以推出操作唯一性，即不存在最小化的说法，只需要找出合法操作即可。

0x01 抽象矩阵

为了标示和观察所有的 x,y 参数。可以将这些参数放入一个矩阵中：对于每一个 x_i,y_i 令 F_{x_i,y_i} 为 1；其余格子否则为 0。

可以发现一对 \left(p,q,w\right) 可以抽象为一种矩阵乘法运算。假若有这样一种矩阵乘法可以使得，为 1 的格子乘 w 还是 w 并进行对应的异或；为 0 的格子乘上了 w 还是 0 这样异或操作则不会发生。

显然定义这样的操作为：

若

A\times B=C

则

C_{i,j}=\bigoplus_{x=0}^{2^k}\bigoplus_{y=0}^{2^k} A_{x,y}\times B_{(x-i)\bmod 2^k,(y-i)\bmod 2^k}

这样即可实现想要的操作。

由于操作自反性且目标为全 0 矩阵，现在我们的目标就是找到答案矩阵 Ans 使得：

A=F\times Ans

也就是：

Ans=A\times F^{-1}

在重载的定一下找到一个 F 的逆矩阵即可。

0x03 矩阵求逆

令单位矩阵为 I，即任意矩阵 M，有 I\times M=M，显然 I_{0,0}=1 其余位置是 0。

猜想 F^{2^k}=I。证明：

  1. 容易观察到 F^{2^k} 只有 F_{2^k\times i\bmod 2^k,2^k\times j\bmod 2^k} 可能有值，即只有 F_{0,0} 可能有值且为 1。

  3. 由于原来 F 只有奇数个值，那么 F^2 也只能有奇数个值因为若有 2\times x_i\equiv 2\times x_j 时，一定会有两个值会被同时异或抵消，这样奇偶数性质不变。

综上可得：

F^{2^k}=I

那么

F^{2^k-1}=F^{-1}

这样得到了一个很劣的时间复杂度 \mathcal{O}\left(2^{5k}\right)。但是至少能算了。

0x04 加速计算

使用类似于快速幂的方法二进制分解 2^k-1，这样只需要 \mathcal{O}\left(k\right) 次乘法，但是还是过不了。进而想到优化乘法。

大力观察题目发现 t 很小，也就是说 F 中的 1 很少，而且肯定越乘越少。这样当 F_{i,j} 没有值的时候就不枚举剩下两维了，这样单次乘法 \mathcal{O}\left(2^{2k}\right)。总时间复杂度达到了 \mathcal{O}\left(kt4^k\right)。

0x05 代码实现

注意不要弄反乘法顺序了，要把 F 放在前面，不然时间复杂度无法保证。

AC CODE


#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE long long
#define OUTPUT_DATA_TYPE int
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){register char s[20];register int i=0;if(x<0){x=-x;putchar('-');}if(x==0){putchar('0');return;}while(x){s[i++]=x%10;x/=10;}while(i){putchar(s[--i]+'0');}return;}

int k,n,mask;

struct MAT{
    long long mat[512][512];
    void setOne(){
        register int i,j;
        for(i=0;i<n;++i)
            for(j=0;j<n;++j) mat[i][j]=0;
        mat[0][0]=1;
        return;
    }

    MAT operator * (MAT another) const{
        register int i,j,k,l;
        register MAT ans;
        ans.setOne();
        ans.mat[0][0]=0;
        for(i=0;i<n;++i)
            for(j=0;j<n;++j)
                if(mat[i][j])
                    for(k=0;k<n;++k)
                        for(l=0;l<n;++l)
                            ans.mat[(i+k)&mask][(j+l)&mask]^=mat[i][j]*another.mat[k][l];
        return ans;
    }

}A,F;

signed main(){
    #ifndef ONLINE_JUDGE
    freopen("name.in", "r", stdin);
    freopen("name.out", "w", stdout);
    #endif

    register int i,j,x,y,res=0;
    k=read();
    n=1<<k;
    mask=n-1;

    for(i=0;i<n;++i)
        for(j=0;j<n;++j)
            A.mat[i][j]=read();

    int q=read();

    for(i=0;i<q;++i){
        x=read()-1;
        y=read()-1;
        F.mat[x][y]^=1;
    }

    for(i=0;i<k;++i){
        A=F*A;
        F=F*F;
    }

    for(i=0;i<n;++i)
        for(j=0;j<n;++j)
            res+=(A.mat[i][j]!=0);

    print(res);

    #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}

总结

这种题要观察到其是矩阵异或乘法这样的性质，并分析这样的操作，善于观察才能完成。