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

即可。

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

矩乘时，在 $a_{x,y}=0$ 的时候不做下面的枚举。
把取模改成位运算。

代码和讲解稍有出入：

CPP

#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;
}
/*

*/

CF1270I Xor on Figures 题解

文章操作

相关推荐

评论

CF1270I Xor on Figures 题解