AcWing 3164. 线性基
原题链接
中等
作者:
皓首不倦
,
2021-05-04 16:36:43
,
所有人可见
,
阅读 523
'''
思路:
把每一个数值看作63位的01向量,把所有向量求线性基,原问题里面选择的向量的异或和在线性基里面选向量做异或和是等价的,异或要最大,就需要
优先保证高位是1,刚好就是线性基里面每一个向量都取1个,就可以构造出一个最优解,这个最优解刚好所有能取1的高位都是1,线性基里面任何一个
向量取0个或者取多于1个,都不可能构造出更好的解
'''
T = int(input())
arr = list(map(int, input().split()))
# 高斯消元
n = len(arr)
lines = min(63, n)
# 基于异或计算求线性基
k = 0 # 非0行计数
for bit in range(62, -1, -1):
if arr[k] & (1 << bit) == 0:
for j in range(k+1, n):
if arr[j] & (1 << bit) != 0:
arr[k], arr[j] = arr[j], arr[k]
# 当前的bit没有找到该位是1的向量,说明当前这一位所有向量都是0,这一位没有携带任何信息,直接跳过这一位
if arr[k] & (1 << bit) == 0:
continue
for j in range(n):
if j != k and arr[j] & (1 << bit) != 0:
arr[j] ^= arr[k]
# 新组出来一个非0行向量,非0向量的个数是基的大小,不可能超过总的向量数
k += 1
if k == n:
break
# 线性基里面的向量全部异或在一起就是答案
ans = 0
for i in range(k):
ans ^= arr[i]
print(ans)