线性基

线性基是一个神奇的东西!!……

定义:

  设数集T的值域范围为[1,2n?1]
  T的线性基是TT的一个子集A={a1,a2,a3,...,an}
  A中元素互相xor所形成的异或集合,等价于原数集TT的元素互相xor形成的异或集合。
  可以理解为将原数集进行了压缩。

性质:

  1.设线性基的异或集合中不存在0。
  2.线性基的异或集合中每个元素的异或方案唯一,其实这个跟性质1是等价的。
  3.线性基二进制最高位互不相同。
  4.如果线性基是满的,它的异或集合为[1,2n-1]。
  5.线性基中元素互相异或,异或集合不变。

一个十分玄学,但很好理解的算法,没什么好说的,感性理解。

 

作者:ezoiLZH
本文版权归作者和博客园所有,欢迎转载,只要写明原文链接即可(^_^)。
原文地址:https://www.cnblogs.com/ezoiLZH/p/9381798.html