AcWing 884. 高斯消元解异或线性方程组python3
原题链接
简单
作者:
xanxus1111
,
2020-06-17 16:40:34
,
所有人可见
,
阅读 615
# 消成上三角矩阵
# 1.枚举列
# 2.找非零行
# 3.交换
# 4.下面消零
# 判断解的三种情况
def gauss(n):
r = 0
for c in range(n):
t = r
#找到非0行
for i in range(r,n):
#如果i行c列不是0
if a[i][c] :
t = i
break
#如果找不到i行c列不是0
if not a[t][c]: continue
#如果找到非零行,那么和当前行交换
for i in range(c,n+1):a[t][i],a[r][i] = a[r][i],a[t][i]
#然后用r行把下面所有行的当前列消成0
for i in range(r+1,n):
#如果i行c列不是0
if a[i][c]:
#那么从第c列开始消
for j in range(c,n+1):
a[i][j] ^= a[r][j]
r += 1
if r < n:
for i in range(r,n):
#如果等号右边不是零 那么无解
if a[i][n]:
return 2
#如果后面行全是零,那么无穷解
return 1
#如果有解那么从下往上消元
for i in range(n,-1,-1):
for j in range(i+1,n):
#a[j][n]是j行的解
a[i][n] ^= a[i][j] & a[j][n]
return 0
if __name__ == "__main__":
n = int(input())
a = [0]*n
for i in range(n):
a[i] = list(map(int,input().split()))
res = gauss(n)
if res == 1:
print('Multiple sets of solutions')
elif res == 2:
print('No solution')
else:
for i in range(n): print(a[i][n])