高斯消元，可以直接消的
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstring> 5 #define MAXN 45*45 6 #define For(i,x,y) for(register int i=x;i<=y;i++) 7 using namespace std; 8 int X,Y; 9 int a[MAXN][MAXN]; 10 int c(int x,int y){return (x-1)*Y+y;} 11 int d[5]={0,-1,0,1,0}; 12 void init(){ 13 scanf("%d%d",&X,&Y); 14 int x,y; 15 For(i,1,X){ 16 For(j,1,Y){ 17 a[c(i,j)][c(i,j)]=1; 18 For(k,0,3){ 19 x=i+d[k],y=j+d[k+1]; 20 if(1<=x&&x<=X&&1<=y&&y<=Y){ 21 a[c(i,j)][c(x,y)]=1; 22 } 23 } 24 a[c(i,j)][c(X,Y)+1]=0; 25 } 26 } 27 } 28 int ans[45][45]; 29 void guass(int m,int n){ 30 int line=1; 31 For(k,1,m){ 32 int i=line; 33 while(i<=m&&!a[i][k])i++; 34 if(i>m){ 35 for(i=1;i<line;i++){ 36 if(a[i][k])a[i][n]^=1,a[i][k]=0; 37 } 38 continue; 39 } 40 if(i!=line)swap(a[i],a[line]); 41 for(i=1;i<=m;i++){ 42 if(i==line)continue; 43 if(a[i][k]){ 44 For(j,k,n){ 45 a[i][j]^=a[line][j]; 46 } 47 } 48 } 49 line++; 50 } 51 line=1; 52 For(i,1,X){ 53 For(j,1,Y){ 54 if(a[line][c(i,j)]){ 55 ans[i][j]=a[line][n]; 56 line++; 57 } 58 else{ 59 ans[i][j]=1; 60 } 61 } 62 } 63 } 64 void solve(){ 65 guass(c(X,Y),c(X,Y)+1); 66 For(i,1,X){ 67 For(j,1,Y-1){ 68 printf("%d ",ans[i][j]); 69 } 70 printf("%d ",ans[i][Y]); 71 } 72 } 73 int main() 74 { 75 // freopen("data.in","r",stdin); 76 init(); 77 solve(); 78 return 0; 79 }
注意到第一行会决定第二行，第二行会决定第三行，然后处理最后一行，让它符合即可，这样方程数目少了一个平方
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstring> 5 #define MAXN 45 6 #define For(i,x,y) for(register int i=x;i<=y;i++) 7 #define ll long long 8 using namespace std; 9 int X,Y; 10 ll t[MAXN][MAXN]; 11 int a[MAXN<<1][MAXN]; 12 int ans[MAXN][MAXN]; 13 void guass(int n,int m){ 14 int line=1; 15 For(k,1,n){ 16 int i=line; 17 while(i<=n&&!a[i][k])i++; 18 if(i>n){ 19 for(i=line-1;i>=1;i--){ 20 if(a[i][k])a[i][m]^=1,a[i][k]=0; 21 } 22 continue; 23 } 24 if(i!=line)swap(a[i],a[line]); 25 for(i=1;i<=n;i++){ 26 if(i==line)continue; 27 if(a[i][k]){ 28 For(j,k,m){ 29 a[i][j]^=a[line][j]; 30 } 31 } 32 } 33 line++; 34 } 35 line=1; 36 For(k,1,n){ 37 if(a[line][k]){ 38 ans[1][k]=a[line][m]; 39 line++; 40 } 41 else{ 42 ans[1][k]=1; 43 } 44 } 45 } 46 void init(){ 47 scanf("%d%d",&X,&Y); 48 For(i,1,Y)t[1][i]=(1LL<<(i-1)); 49 For(i,2,X+1){ 50 For(j,1,Y){ 51 t[i][j]=t[i-1][j-1]^t[i-1][j]^t[i-1][j+1]^t[i-2][j]; 52 } 53 } 54 ll p;int k; 55 For(j,1,Y){ 56 for(p=t[X+1][j],k=1;p;p>>=1,k++){ 57 if(p&1){ 58 a[j][k]=1; 59 } 60 } 61 } 62 } 63 void solve(){ 64 guass(Y,Y+1); 65 // for(int i=1;i<=Y;i++){ 66 // for(int j=1;j<=Y+1;j++){ 67 // printf("%d ",a[i][j]); 68 // } 69 // printf(" "); 70 // } 71 For(i,2,X){ 72 For(j,1,Y){ 73 ans[i][j]=ans[i-1][j-1]^ans[i-1][j]^ans[i-1][j+1]^ans[i-2][j]; 74 } 75 } 76 For(i,1,X){ 77 For(j,1,Y-1){ 78 printf("%d ",ans[i][j]); 79 } 80 printf("%d ",ans[i][Y]); 81 } 82 } 83 int main() 84 { 85 // freopen("data.in","r",stdin); 86 init(); 87 solve(); 88 return 0; 89 }