CF1270I Xor on Figures

有个矩阵(A)，下标循环。给出个坐标集合(F)。每次可以选择一个点((i,j))，使(A_{i+x,j+y})异或(p)，(p)为自己定的一个数，每次可以不同。

问最少的操作次数。

矩阵大小为(2^k*2^k)。

(kle 9,|F|le 99)

(|F|)为奇数。

---

感觉好像看过但是还是不会……看题解好像好简单啊怎么直接抽代就完事了。

定义运算(A*B)，表示((A*B)_{x,y}=sum_{i,j}A_{i,j}B_{x-i,y-j})。

于是题目相当于，找到(C)使得(C*F=A)。其中(C)的非零位置尽量少。

以下证明(F)存在逆元，且(F^{-1}=F^{2^k-1})。于是(C=A*F^{2^k-1})，此时(C)唯一跟最小根本就没有关系。暴力算即可。

观察到(F^2)中，有值的位置只有((2x_i,2y_i))。因为((x_i,y_i),(x_j,y_j),i eq j)的贡献会被算两次被抵消。于是(F^{2^k})中只有((0,0))处有值，并且这个值一定为(1)，因为(|F|)为奇数。

---

using namespace std;
#include <bits/stdc++.h>
#define K 9
#define N (1<<K)
#define ll long long
int k,n;
ll a[N][N];
int m;
struct DOT{
	int x,y;
} d[105];
int main(){
//	freopen("in.txt","r",stdin);
	scanf("%d",&k);
	n=1<<k;
	for (int i=0;i<n;++i)
		for (int j=0;j<n;++j)
			scanf("%lld",&a[i][j]);
	scanf("%d",&m);
	for (int i=0;i<m;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		--x,--y;
		d[i]={x,y};
	}
	for (int t=0;t<k;++t){
		static ll b[N][N];
		memcpy(b,a,sizeof a);
		memset(a,0,sizeof a);
		for (int i=0;i<n;++i)
			for (int j=0;j<n;++j)
				for (int l=0;l<m;++l)
					a[i+d[l].x&n-1][j+d[l].y&n-1]^=b[i][j];
		for (int l=0;l<m;++l)
			d[l]={d[l].x<<1&n-1,d[l].y<<1&n-1};
	}
	int ans=0;
	for (int i=0;i<n;++i)
		for (int j=0;j<n;++j)
			ans+=(a[i][j]!=0);
	printf("%d
",ans);
	return 0;
}