SPOJ卡常也太可怕了吧……\(O((\frac{n+m}{32})^3)\)卡100ms，这都什么人啊.jpg

关于这题，设格子\((x,y)\)上原来的数为\(a[x][y]\)，对格子操作为\(f[x][y]\)

则有

\(\oplus_{i=1}^n f[i][y]\; xor \;\oplus_{i=1}^m f[x][i]\;xor\;f[x][y]\;xor\;a[x][y]=0\)

两边异或\(a[x][y]\)

\(\oplus_{i=1}^n f[i][y]\; xor \;\oplus_{i=1}^m f[x][i]\;xor\;f[x][y]=a[x][y]\)

于是就有了一个\(O((\frac{nm}{3})^3)\)的做法

观察发现，对于一个矩形上的四个角，知道任意三个角的操作状态，就能推出第四个角的操作状态

即

\(f[x1][y1]\;xor\;f[x2][y1]\;xor\;f[x1][y2]\;xor\;f[x2][y2]=a[x1][y1]\;xor\;a[x2][y1]\;a[x1][y2]\;xor\;a[x2][y2]\)

于是就只用解出第一行第一列的所有操作情况就行了。

高斯消元

calc的意思是：

对于一个点\((x,y)\),列出方程

\(f[1][y]\;xor\;f[x][1]\;xor\;f[x][y]\;xor\;f[1][1]=a[1][y]\;xor\;a[x][1]\;a[x][y]\;xor\;a[1][1]\)

然后把它异或到\((1,y)\)和\((x,1)\)对应的方程上，相当于预处理操作状态。

代码（无耻地开了各种优化）：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize("Ofast")#include 
    
     #define N 1010#define il inline#define re registerusing namespace std;int a[N][N],b[N][N],n,m;bitset< N<<1 > f[N<<1];static char buf[100000],*p1=buf,*p2=buf;#define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++inline int read(){    register int x(0);register char c(gc);    while(c>'9'||c<'0')c=gc;    while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+(c^48),c=gc;    return x;}il void calc(int x,int y,int id){    f[id][1].flip(),f[id][x].flip(),f[id][y+n-1].flip();    if(a[1][1]^a[x][1]^a[1][y]^a[x][y]) f[id][n+m].flip();}il void gauss(){    re int i,j;    for(i=1;i<=n+m-1;++i){        if(!f[i][i]){            for(j=i+1;j<=n+m-1;++j)                if(f[j][i]){ swap(f[i],f[j]);break; }            if(!f[i][i]) continue;        }        for(j=1;j<=n+m-1;++j)            if(f[j][i] && i!=j) f[j]^=f[i];     }}int main(){//    freopen("tmp.txt","r",stdin);    re int i,j;    n=read(),m=read();    for(i=1;i<=n;++i){        for(j=1;j<=m;++j){            char c(gc);a[i][j]=c&1;        }gc;            }    f[1][n+m]=a[1][1];    for(i=1;i<=n+m-1;++i) f[1].set(i);    for(i=2;i<=n;++i){        f[i].set(1),f[i][n+m]=a[i][1];        for(j=2;j<=n;++j) f[i].set(j);        //处理f[i][1]        //列的变化是不管的，因为没有一维为1    }    for(i=n+1;i<=n+m-1;++i){        f[i].set(1),f[i][n+m]=a[1][i-n+1];        for(j=n+1;j<=n+m-1;++j) f[i].set(j);        //处理f[1][i]    }     for(i=2;i<=n;++i)        for(j=2;j<=m;++j)            calc(i,j,i),calc(i,j,j+n-1);    gauss();    for(i=1;i<=n;++i) b[i][1]=f[i][n+m];    for(i=n+1;i<=n+m-1;++i) b[1][i-n+1]=f[i][n+m];    for(i=1;i<=n;++i){        for(j=1;j<=m;++j){            if(i>1 && j>1)                b[i][j]=a[1][1]^a[i][1]^a[1][j]^a[i][j]^b[1][1]^b[i][1]^b[1][j];            putchar(b[i][j]+'0');        }        puts("");    }}