【贪心】【P2117】小Z的矩阵

传送门

Description

小Z最近迷上了矩阵，他定义了一个对于一种特殊矩阵的特征函数G。对于N*N的矩阵A，A的所有元素均为0或1，

当然询问一个矩阵的G值实在是太简单了。小Z在给出一个N*N矩阵的同时将给你Q个操作，操作描述如下：

操作1：形如一个整数1和一个整数x，表示将第x行的元素全部“翻转”。

操作2：形如一个整数2和一个整数x，表示将第x列的元素全部“翻转”。

操作3：形如一个整数3，表示询问当前矩阵的特征值G。

“翻转”的定义为将1变成0，将0变成1。

Input

第1行：两个正整数N，Q。 N表示矩阵的行数(列数)，Q表示询问的个数。

接下来N行：一个N*N的矩阵A，0<=A[i][j]<=1。

接下来Q行：Q个操作。

Output

一行若干个数，中间没有空格，分别表示每个操作的结果（操作1和操作2不需要输出）。

Sample Input

Sample Output

Hint

30% N<=100, Q<=10^5

100% N<=1,000, Q <=5*10^5

Solution

对于30%，O(NQ)暴力出奇迹

对于100%，我们考虑这样一个事实：对于所有的i!=j，会计算四次A，其中通过(i,j)计算A[i][j]*A[j][i],，通过(j,i)计算A[j][i]*A[i][j]。不难发现，无论A[i][j]*A[j][i]等于0还是等于1，相加后取模2恒等于零。

数学证明如下：对于ans=Σ(A[i][j]*A[j][i]+A[i][j]*A[j][i])(i<j) Mod 2=Σ2(A[i][j]*A[j][i]) Mod 2=2*Σ(A[i][j]*A[j][i]) Mod 2=0

所以对于i!=j矩阵元素对答案没有贡献。

所以ans=ΣA[i][i] Mod 2。每次修改 ans^=1即可。

Code

#include<cstdio>
#define ci const int

inline void qr(int &x) {
    char ch=getchar(),lst=NULL;
    while(ch>'9'||ch<'0') lst=ch,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if (lst=='-') x=-x;
}

char buf[20];
inline void write(int x,const char aft,const bool pt) {
    if(x<0) {putchar('-');x=-x;}
    int top=0;
    do {
        buf[++top]=x%10+'0';
        x/=10;
    } while(x);
    while(top) putchar(buf[top--]);
    if(pt) putchar(aft);
}

template <typename T>
inline T mmax(const T &a,const T &b) {if(a>b) return a;return b;}
template <typename T>
inline T mmin(const T &a,const T &b) {if(a<b) return a;return b;}
template <typename T>
inline T mabs(const T &a) {if(a<0) return -a;return a;}

template <typename T>
inline void mswap(T &a,T &b) {T temp=a;a=b;b=temp;}

int n,m,a;
bool ans;

int main() {
    qr(n);qr(m);
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j) qr(a);else {a=0;qr(a);if(a) ans^=1;}
    while(m--) {a=0;qr(a);if(a==3) {if(ans) putchar('1');else putchar('0');}else {qr(a);ans^=1;}}
    putchar('
');
    return 0;
}

Summary

对于计算了两遍然后答案Mod 2的元素，可以直接pass。

真tm神仙