【BZOJ 3503】 [Cqoi2014]和谐矩阵

3503: [Cqoi2014]和谐矩阵

Time Limit: 10 Sec Memory Limit: 128 MBSec Special Judge Submit: 493 Solved: 216 [Submit][Status][Discuss] Description

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

Input

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

Output

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

Sample Input

4 4

Sample Output

0100

1110

0001

1101

数据范围

1 <=m, n <=40 HINT

Source

鸣谢Ljcc提供Spj

高斯消元解异或方程组（具体做法见【POJ 1222】）。

有两种做法： ①速度较慢的方法： 对于矩阵中的每一个元素都可以列出一个方程，表示第

;int a[2000][2000],ans[2000],d[10][5],id[50][50],n,m;void Gauss(int n,int m){for (int i=1;i<=n;i++){int j;for (j=i;j<=m&&!a[j][i];j++);if (j>n) continue;if (j!=i)for (int k=i;k<=m;k++)swap(a[i][k],a[j][k]);for (int j=i+1;j<=n;j++)if (a[j][i])for (int k=i;k<=m;k++)a[j][k]^=a[i][k];}for (int i=n;i;i–){if (!a[i][i]){ans[i]=1;continue;}for (int j=i+1;j<=n;j++)a[i][m]^=(ans[j]*a[i][j]);ans[i]=a[i][m];}}int main(){int n,m;scanf(“%d%d”,&n,&m);d[0][1]=d[0][2]=0;d[1][1]=d[2][1]=0,d[1][2]=1,d[2][2]=-1;d[3][2]=d[4][2]=0,d[3][1]=1,d[4][1]=-1;int cnt=0;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)id[i][j]=++cnt;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)for (int k=0;k<=4;k++){int p=id[i+d[k][1]][j+d[k][2]];if (p) a[id[i][j]][p]=1;}Gauss(cnt,cnt+1);cnt=0;for (int i=1;i<=n;i++){printf(“%d”,ans[++cnt]);for (int j=2;j<=m;j++)printf(” %d”,ans[++cnt]);printf(“\n”);}return 0;}

②速度快的办法： 可以发现当第一行确定之后，整个矩阵就确定了，，因此我们只要把第一行设为未知数即可。

如何判断第一行的某种排列是否合题意？

如果第m+1行全部是0就合题意，否则不合。

而第m+1行的每一个数一定是第一行的某些数异或起来的，我们只要只要确定他是由哪些数异或得到（求出关系数组），使这些数的异或值为0即可。

最终列出n个方程，有n个未知数。（orz zyf-zyf）

;LL b[45][45];int a[45][45],ans[45][45],n,m;void Gauss(){for (int i=1;i<=m;i++){int j;for (j=i;j<=m&&!a[j][i];j++);if (j>m) continue;if (j!=i)for (int k=i;k<=m+1;k++)swap(a[i][k],a[j][k]);for (int j=i+1;j<=m;j++)if (a[j][i])for (int k=i;k<=m+1;k++)a[j][k]^=a[i][k];}for (int i=m;i;i–){if (!a[i][i]){ans[1][i]=1;continue;}for (int j=i+1;j<=m;j++)a[i][m+1]^=(ans[1][j]*a[i][j]);ans[1][i]=a[i][m+1];}}int main(){scanf(“%d%d”,&n,&m);for (int i=1;i<=m;i++)b[1][i]=(LL)1<<(i-1);for (int i=2;i<=n+1;i++)for (int j=1;j<=m;j++)b[i][j]=b[i-1][j-1]^b[i-1][j]^b[i-1][j+1]^b[i-2][j];for (int i=1;i<=m;i++)for (int j=1;j<=m;j++)a[i][j]=(b[n+1][i]>>(j-1))&1;Gauss();for (int i=1;i<=m;i++)printf(“%d “,ans[1][i]);printf(“\n”);for (int i=2;i<=n;i++){for (int j=1;j<=m;j++){ans[i][j]=ans[i-1][j-1]^ans[i-1][j]^ans[i-1][j+1]^ans[i-2][j];printf(“%d “,ans[i][j]);}printf(“\n”);}return 0;}

感悟： 高斯消元解异或方程组：方程中异或相当于相加，于是异或方程就变成了普通的方程； 列异或方程通常要先求出关系数组，给每个数乘上他们的关系，1表示有影响，0表示没有影响。

在乎的是看风景的心情，旅行不会因为美丽的风景终止。