线性基

What · 是什么

线性基是线性空间的一组基（极大线性无关组）。竞赛中常用异或线性基（GF(2)域上的基）：给定一组数，构造一组基使得任意数的子集异或都能由基的子集异或表示。性质：基中任意非空子集异或不为0；基中各数二进制最高位不同。支持查询最大/最小/第k小异或值、判断某数能否被异或表出、求异或值排名等。

Why · 为什么

How · 实现

伪代码

insert(x):
  for i in bits-1..0:
    if x>>i&1:
      if basis[i]==0: basis[i]=x; return True
      x ^= basis[i]
  return False

max_xor(start):
  ans = start
  for i in bits-1..0:
    if ans^basis[i] > ans: ans^=basis[i]
  return ans

Python 实现

class XorBasis:
    """XOR linear basis over GF(2). Supports max/min/kth XOR queries."""
    def __init__(self, bits=60):
        self.basis = [0] * bits
        self.bits = bits
        self.size = 0

    def insert(self, x):
        """Insert x into the basis. Returns True if rank increased."""
        for i in range(self.bits - 1, -1, -1):
            if not (x >> i & 1):
                continue
            if self.basis[i] == 0:
                self.basis[i] = x
                self.size += 1
                return True
            x ^= self.basis[i]
        return False

    def max_xor(self, start=0):
        """Maximum XOR of any subset, starting from given value."""
        ans = start
        for i in range(self.bits - 1, -1, -1):
            if (ans ^ self.basis[i]) > ans:
                ans ^= self.basis[i]
        return ans

    def min_xor(self):
        """Minimum nonzero XOR of any subset."""
        for i in range(self.bits):
            if self.basis[i] != 0:
                return self.basis[i]
        return 0

    def contains(self, x):
        """Check if x can be represented as XOR of some subset."""
        for i in range(self.bits - 1, -1, -1):
            if (x >> i & 1) and self.basis[i]:
                x ^= self.basis[i]
        return x == 0

    def kth_xor(self, k):
        """k-th smallest XOR value (1-indexed). Requires reduction first."""
        self._reduce()
        ans = 0
        cnt = 0
        for i in range(self.bits):
            if self.basis[i]:
                if (k >> cnt) & 1:
                    ans ^= self.basis[i]
                cnt += 1
        return ans

    def _reduce(self):
        """Reduce basis to simplified row echelon form."""
        for i in range(self.bits - 1, -1, -1):
            if self.basis[i]:
                for j in range(i + 1, self.bits):
                    if self.basis[j] & (1 << i):
                        self.basis[j] ^= self.basis[i]

if __name__ == "__main__":
    xb = XorBasis(20)
    for x in [633, 211, 169, 841, 1008]:
        xb.insert(x)
    assert xb.max_xor() > 0
    assert xb.contains(633)
    assert xb.contains(633 ^ 211)
    assert not xb.contains(633 ^ 211 ^ 999)  # 999 not in span
    # Empty basis
    xb2 = XorBasis(10)
    assert xb2.max_xor(5) == 5  # start value when basis empty
    assert xb2.min_xor() == 0
    # k-th XOR
    xb3 = XorBasis(10)
    for x in [1, 2, 4]:
        xb3.insert(x)
    xb3._reduce()
    # All XOR values: 0,1,2,3,4,5,6,7 sorted
    assert xb3.kth_xor(1) == 1
    assert xb3.kth_xor(2) == 2
    assert xb3.kth_xor(4) == 4
    print("linear-basis: ALL TESTS PASSED")

易错点

• 插入顺序不影响基的大小（rank），但影响基的具体值
• 求第k小前必须调用_reduce化简为简化阶梯形
• 空基的最大异或查询返回start值本身
• min_xor返回最小非零异或值，空集异或为0不计

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/linear-algebra/basis/
• 洛谷✓ https://www.luogu.com.cn/problem/P3812