Linear Basis

线性基

构造方法

• 逆序枚举 $ t $ 所有为 $ 1 $ 的二进制位 $ j = L $，对于每个 $ j $
  • 如果 $ a_j $，则令 $ t = t a_j $
  • 如果 $ a_j = 0 $，则
    • 枚举 $ k [0, j) $，如果 $ t $ 的第 $ k $ 位为 $ 1 $，则令 $ t = t a_k $
    • 枚举 $ k (j, L] $，如果 $ a_k $ 的第 $ j $ 位为 $ 1 $，则令 $ a_k = a_k t $
    • 令 $ a_j = t $，结束插入过程

*注意: 加粗的步骤保证了特殊性质.

特殊性质

如上构造的线性基具有很优秀的性质:

每一行要么是空行, 要么a[k]==1并且只有\(i\gt k\) 并且不在线性基中的位\(i\)才有可能为1. 于是看一个数是否属于线性空间, 只需要异或上 存在于线性基中的元素 ,看其他位置是否全0.

题目

2018-2019, ICPC, Asia Yokohama Regional Contest 2018 Problem I - Ranks

参考文献: 线性基学习笔记 | Menci's Blog