AcWing 884. java同学详解
原题链接
简单
作者:
季之秋
,
2021-02-07 21:40:48
,
所有人可见
,
阅读 696
import java.util.*;
public class Main{
static int n;
static int a[][]=new int[110][110];
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
for(int i=0;i<n;i++){
for(int j=0;j<=n;j++)
a[i][j]=sc.nextInt();
}
int t=gauss();
if(t==1){
for(int i=0;i<n;i++){
System.out.println(a[i][n]);
}
}else System.out.println(t==2?"No solution":"Multiple sets of solutions");
}
static int gauss(){
int c=0,r=0;
for(;c<n;c++){
int t=r;
for(int i=r;i<n;i++) if(a[i][c]!=0) {t=i;break;}//找出最大值1
if(a[t][c]==0) continue;//c列都是0就跳过
for(int i=c;i<=n;i++){ //交换置顶
int q=a[r][i];
a[r][i]=a[t][i];
a[t][i]=q;
}
for(int i=r+1;i<n;i++){ //下行的所有第c列变0
if(a[i][c]!=0)//(1^0==1) 所有防止误判
for(int j=c;j<=n;j++){
a[i][j]^=a[r][j]; //(1^1=0),把1变成0,至于为什么可以^等式不变呢
//假设a^b^c=D,x^y^z=T,那么a^b^c^(x^y^z)=T^D
//等式还是成立的,变成(a^x) ^ (b^y) ^ (c^z)=T^D
}
}
r++;
}
if(r<n){
for(int i=r;i<n;i++) if(a[i][n]!=0) return 2;
return 3;
}
for(int i=r-1;i>=0;i--){
for(int j=i+1;j<n;j++){
a[i][n]^=a[i][j]&a[j][n];//(1)因为只有1或0,所以*和&一样
//(2)a^b=c,c^b=a;
}
}
return 1;
}
}