bzoj3503 和谐矩阵

Description

我们称一个由0和1组成的矩阵是和谐的，当且仅当每个元素都有偶数个相邻的1。一个元素相邻的元素包括它本
身，及他上下左右的4个元素（如果存在）。
给定矩阵的行数和列数，请计算并输出一个和谐的矩阵。注意：所有元素为0的矩阵是不允许的。

Input

输入一行，包含两个空格分隔的整数m和n，分别表示矩阵的行数和列数。

Output

输出包含m行，每行n个空格分隔整数（0或1），为所求矩阵。测试数据保证有解。

设(x,y)为某个位置的取值（出界视为0），则有(x,y)^(x-1,y)^(x+1,y)^(x,y-1)^(x,y+1)=0

即(x^y)=(x-1,y-1)^(x,y-1)^(x+1,y-1)^(x,y-2)

由此确定矩阵第一行即确定了整个矩阵，若合法则矩阵第m+1行计算结果为全0 (不全0则第m行不合法)。

设第一行为未知数，计算出第m+1行由第一行哪些位置的值异或得到，建立异或方程组，高斯消元求解即可。

若一个元无法确定则定为1。

时间复杂度O(n²m+n³)，若数据规模更大则可以考虑压位。

#include<cstdio>
int n,m;
int f[50][50][50];
int xs[50][50],ys[50],as[50];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)f[1][i][i]=1,as[i]=1;
    for(int i=2;i<=m+1;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++)f[i][j][k]=f[i-1][j-1][k]^f[i-1][j][k]^f[i-1][j+1][k]^f[i-2][j][k];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)xs[i][j]=f[m+1][i][j];
    }
    int w=1;
    for(int i=1;i<=n;i++){
        for(int j=w;j<=n;j++){
            if(xs[j][i]){
                for(int k=1;k<=n;k++){int a=xs[j][k];xs[j][k]=xs[w][k];xs[w][k]=a;}
                int c=ys[j];ys[j]=ys[w];ys[w]=c;
                break;
            }
        }
        if(!xs[w][i])continue;
        int yv=ys[w];
        for(int j=w+1;j<=n;j++){
            if(xs[j][i]){
                ys[j]^=ys[w];
                for(int k=1;k<=n;k++)xs[j][k]^=xs[w][k];
            }
        }
        w++;
    }
    for(int i=n;i>=1;i--){
        int mx=1;
        while(mx<=n&&!xs[i][mx])mx++;
        if(mx>n)continue;
        for(int j=mx+1;j<=n;j++){
            if(xs[i][j])xs[i][j]=0,ys[i]^=as[j];
        }
        as[mx]=ys[i];
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            int v=0;
            for(int k=1;k<=n;k++)if(as[k]&&f[i][j][k])v^=1;
            printf("%d ",v);
        }
        putchar(10);
    }
    return 0;
}