题目描述
我们称一个由0和1组成的矩阵是和谐的，当且仅当每个元素都有偶数个相邻的1。一个元素相邻的元素包括它本身，及他上下左右的4个元素（如果存在）。给定矩阵的行数和列数，请计算并输出一个和谐的矩阵。注意：所有元素为0的矩阵是不允许的。
分析： 1.这种矩阵的，一个元素和它上下左右有关系的，一般都是高斯消元。 2.把题目转化为亦或方程：因为知道第一行的情况后，后面的都可以递推，所以一直推到第n+1行。根据这一行的数都为0列出方程。 3.再高斯消元啦。
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;typedef long long LL;const int maxn=50;LL a[maxn][maxn],ans[maxn][maxn],b[maxn][maxn];int n,m;void Gauss(){ for(int i=1;i<=m;i++){ int j=i; while(j<=m && !a[j][i]) j++; if(j>m) continue; if(i!=j) for(int k=1;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>=1;i--){ if(!a[i][i]){ ans[1][i]=1LL;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]=(1LL<<(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-2][j]^b[i-1][j+1]; for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) a[i][j]=(b[n+1][i]>>(j-1) & 1LL); Gauss(); for(int i=1;i<=m;i++) PRintf("%lld%c",ans[1][i],i==m?'/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-2][j]^ans[i-1][j+1]; } for(int j=1;j<=m;j++) printf("%lld%c",ans[i][j],j==m?'/n':' '); } return 0;}^_^
新闻热点
疑难解答
