AcWing 210. 异或运算
原题链接
中等
作者:
皓首不倦
,
2021-05-04 18:59:19
,
所有人可见
,
阅读 512
T = int(input())
for case_idx in range(T):
N = int(input())
arr = list(map(int, input().split()))
M = int(input())
q = list(map(int, input().split()))
# 基于异或计算求线性基
k = 0 # 非0行计数
n = len(arr)
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
# 到此为止求出了包含k个向量的基于异或计算的线性基
has_zero = n > k # 如果向量数超过基的大小,一定有线性相关的向量存在,原向量已经能通过线性组合组合出0向量
print(f"Case #{case_idx+1}:")
for query_k in q:
# 如果原先就能通过异或凑出来0,就考虑求线性基取非全0系数时候能够凑出来的第k-1小的向量
if has_zero:
query_k -= 1
'''
基向量的选择情况和能够组合出来的向量的排序有如下关系:
基向量0 基向量1 基向量2 ........ 基向量k-3 基向量k-2 基向量k-1
0 0 0 0 0 1 能组合出的第1小的向量
0 0 0 0 1 0 能组合出的第2小的向量
0 0 0 ...... 0 1 1 能组合出的第3小的向量
......
由于每一个基向量要么取1个要么取0个,所以组合出来的向量的大小刚好就是符合二进制递增的规律
'''
if query_k == 0:
ans = 0
elif query_k > 2**k - 1:
ans = -1
else:
ans = 0
for bit in range(k):
if query_k & (1 << bit) != 0:
ans ^= arr[k-1-bit]
print(ans)