[cf1270I]Xor on Figures

考虑一个构造：令初始$2^{k} imes 2^{k}$的矩阵为$A$（下标从0开始），再构造一个矩阵$T$，满足仅有$T_{x_{i},y_{i}}=1$（其余位置都为0），定义矩阵卷积$otimes$即
$$
(Aotimes B)_{x,y}=igoplus_{x_{1}+x_{2}equiv x(mod 2^{k}),y_{1}+y_{2}equiv y(mod 2^{k})}A_{x_{1},y_{1}}B_{x_{2},y_{2}}
$$
（不难证明这个卷积运算有交换律和结合律）

令$F$为答案矩阵，即$F_{x,y}$为在$(x,y)$上所选择的$p$（多次选择异或起来即可），根据定义有$Fotimes T=A$

考虑$otimes$运算的单位矩阵$e$，即满足对于任意矩阵$A$，$Aotimes e=A$，不难发现$e_{x,y}=[x=0][y=0]$即满足此条件，以下即以此为单位矩阵

通过单位矩阵，我们就可以对矩阵$T$求逆了，若其求逆结果为$T^{-1}$（即满足$Totimes T^{-1}=e$的矩阵因此），将上式两边同乘$T^{-1}$即有$F=Aotimes T^{-1}$

考虑如何求出$T^{-1}$，似乎并不太好求，那么再考虑一个问题，即$T^{2}$（即$Totimes T$）是一个怎样的矩阵：

根据定义中的式子，注意到当交换$x_{1}$和$x_{2}$、$y_{1}$和$y_{2}$后，两者所贡献的位置以及权值相同，而$oplus$具有自反性，因此即最终结果为0

但特别的，当$x_{1}=x_{2}$且$y_{1}=y_{2}$，显然是不能交换的，即
$$
(T^{2})_{x,y}=igoplus_{2x'equiv x(mod 2^{k}),2y'equiv y(mod 2^{k})}T_{x',y'}^{2}=igoplus_{2x'equiv x(mod 2^{k}),2y'equiv y(mod 2^{k})}T_{x',y'}
$$
（最后一步由于$T$中任意元素都为0或1，因此$T_{x',y'}^{2}=T_{x',y'}$）

上面这个式子通俗的来说，也就是将$T$中的每一个在$(x,y)$的1都移动到$(2x mod 2^{k},2y mod 2^{k})$，当一个位置有两个1可以相互抵消

当然我们也可以先不抵消，重复上述过程，则有
$$
(T^{2^{k}})_{x,y}=igoplus_{2^{k}x'equiv x(mod 2^{k}),2^{k}y'equiv y(mod 2^{k})}T_{x',y'}=[x=0][y=0]igoplus_{x,y}T_{x,y}=[x=0][y=0][t mod 2]
$$
（显然$T$中1的个数恰好为$t$）

根据$t$是奇数，即$T^{2^{k}}=e$，那么$Totimes T^{2^{k}-1}=e$，即$T^{-1}=T^{2^{k}-1}$

关于如何计算$Aotimes T^{2^{k}-1}$，如果暴力计算两个矩阵复杂度是$o(2^{4k})$，即使用快速幂优化$T^{2^{k}-1}$的计算，复杂度也是$o(k2^{4k})$，无法通过

但是，注意到$forall 0le ile k,T^{2^{i}}$至多只有$t$个1（即使移动到的位置都不重合，没有抵消）

根据$2^{k}-1=sum_{i=0}^{k-1}2^{i}$，再根据结合律所求即$Aotimes T^{1}otimes T^{2}otimes...otimes T^{2^{k-1}}$，按照运算顺序从左到右依次乘，每一次复杂度为$o(t2^{2k})$，总复杂度即$o(tk2^{2k})$

（每一个$T^{2^{i}}$怎么求前面应该也已经说明了）

#include<bits/stdc++.h>
using namespace std;
#define N 2005
int n,m,ans,x[N],y[N];
long long a[N][N],b[N][N];
void mul(){
    memset(b,0,sizeof(b));
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<(1<<n);j++)
            for(int k=1;k<=m;k++)b[(x[k]+i)%(1<<n)][(y[k]+j)%(1<<n)]^=a[i][j];
    memcpy(a,b,sizeof(a));
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<(1<<n);j++)scanf("%lld",&a[i][j]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&x[i],&y[i]);
    for(int i=0;i<n;i++){
        mul();
        for(int j=1;j<=m;j++){
            x[j]=2*x[j]%(1<<n);
            y[j]=2*y[j]%(1<<n);
        }
    }
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<(1<<n);j++)
            if (a[i][j])ans++;
    printf("%d",ans);
}