AcWing 884. 高斯消元解异或线性方程组
原题链接
简单
作者:
皓首不倦
,
2020-09-05 14:53:44
,
所有人可见
,
阅读 506
'''
直接模拟计算过程即可
'''
import sys
n = int(input())
m = []
for _ in range(n):
s = sys.stdin.readline().strip()
m.append(list(map(int, s.split())))
# 高斯消元
for col in range(0, n):
max_val, max_row = m[col][col], col
for row in range(col+1, n):
if max_val == 1:
break
if m[row][col] > max_val:
max_val, max_row = m[row][col], row
break
if max_val == 0:
continue
m[col], m[max_row] = m[max_row], m[col]
for row in range(col+1, n):
if m[row][col] == 0:
continue
for j in range(col, n+1):
m[row][j] ^= m[col][j]
flag = 0
ans = [0] * n
for i in range(n-1, -1, -1):
val = m[i][n]
s = 0
for j in range(n-1, i, -1):
if m[i][j] == 1:
s ^= ans[j]
val ^= s
if val == 0 and m[i][i] == 0:
# 多组解
flag = 1
break
if val == 1 and m[i][i] == 0:
# 无解
flag = 2
break
else:
ans[i] = val
if flag == 1:
print('Multiple sets of solutions')
elif flag == 2:
print('No solution')
else:
for val in ans:
print(val)