题解 P2117 【小Z的矩阵】
顾z
2018-09-05 06:27:23
## %%%[troubler](https://www.luogu.org/space/show?uid=88089)
题目描述-->[p2117 小z的矩阵](https://www.luogu.org/problemnew/show/P2117)
## 分析：
题目给定我们一个正方形.
容易想到,正方形是对称的.
**推敲一下**
如果我们的矩阵是这样的↓ ~~闭眼瞎敲出来的.~~
0 1 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 1 0 0
1 1 0 0 1
题目给定我们的计算公式为**a[i][j] $\times $a[j][i]的和**。
对于这个栗子.
按照式子来的话我们这么算
a[1][1]*a[1][1]+a[1][2]*a[2][1]+a[1][3]*
a[3][1]+a[1][4]*a[4][1]+a[1][5]*a[5][1]+
a[2][1]*a[1][2]+a[2][2]*a[2][2]+.......
..............+a[5][5]*a[5][5]
虽然不是手算,但摧残一个计算机你真的忍心嘛emmm
**很容易地发现**~~(一点也不容易~~
a[i][j]*a[j][i]与a[j][i]*a[i][j]的值相同.
如果为1,那么他们加和就是2,%2就变成0.
如果为0,那么他们加和依旧为0,%2依旧为0.
对答案没有贡献!
但是
在我们的对角线上的元素是对答案的贡献是它的平方.
因此我们需要**记录对角线上的元素对答案的贡献**.
即 **除了对角线上的元素,其他位置都没有贡献.**
因此我们可以只记录对角线上的元素的答案.
对于翻转操作,我们~~很容易~~发现
**每一行每一列均对应地控制一个对角线上的元素.**
## 如何统计我们的答案?
按照上面的例子来看,那答案就是1.
如果翻转的话,我们会改变某一位置上的元素的值.
即0->1,1->0
假如,我们改变地是第5行.那我们最后一个元素得到的就是0.
此时答案为0.
如果我们再去翻转其他行/列,我们得到的答案一定是1.
以此类推,我们发现,只要有翻转操作,我们的答案一定会改变.即从0->1,1->0.
所以我们可以定义变量ans,如果有翻转操作,就将它**^=1**
-----------------关于^操作.------------------
**0^1=0,1^1=0.**
观察到它的性质,我们就知道如何记录答案了!
(或者你可以**!**一下
关于^操作,网上有不少讲解,在这里就不展开了.
~~(懒~~
------------------代码---------------------
```cpp
#include<bits/stdc++.h>
#define IL inline
#define RI register int
IL void in(int &x)
{
int f=1;x=0;char s=getchar();
while(s>'9' or s<'0'){if(s=='-')f=-1;s=getchar();}
while(s>='0' and s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,Q,ans;
int main(void)
{
in(n);in(Q);
for(RI i=1;i<=n;i++)
for(RI j=1,c;j<=n;j++)
if(i==j)
in(c),(ans+=c)%=2;
else
in(c);//非对角线上的元素对答案没有贡献,我们只读入.
for(RI i=1,opt,x;i<=Q;i++)
{
in(opt);
if(opt==3)
printf("%d",ans);
else in(x),ans^=1;
}
}
```