标签：组合 无关 异或 线性 向量 性质
线性代数中，我们学过极大线性无关组。
极大线性无关组：在线性空间中拥有向量个数最多的线性无关向量组。
换言之，任取一个子集所表示的向量不能由集合中剩余的向量表示。
在计算机语言中，我们应用在一些方面，称之为线性基。
eg.P3812 【模板】线性基
题意： 给你 n 个数字，取任意个，使它们的异或和最大。
思路：将这 n 个数字转化成 2 进制，每个数字对应一个 01 构成的向量，所有这些向量就构成了一个空间。
原题就转换为求这个向量组的极大线性无关组，也就是求向量基。
首先来证明一个性质：
取向量组中的两个向量 a,b，把 a,b 中的任意一个向量替换成 a xor b，替换前后向量组中的向量的线性组合得到的空间相同。简单来说，替换前后 能异或的值一样。（这就是异或的神奇之处了）。
笔者认为不难证明，感兴趣的同学可自行证明。
所以把向量组里的向量互相异或，极大线性无关向量组的大小是不变的。
基本思想是：从左到右扫描每个向量，对于第 i 个向量的第 j 位，如果前面已经有第 j 位为 1 的向量，那么把第 i 个向量异或那个向量。
这样最后得到的向量组，不考虑 0 向量，最高位的 1 的位置是互不相同的。显然这些向量组无关。
于是这样构造出的极大线性无关组，也就是线性基，具有以下性质：
性质1：最高位 1 的位置互不相同。
性质2：任意一个可以用这些向量组合出的向量 x，组合方式唯一。
prove：假设 x 的组合方法不唯一，也就是说存在一个向量组可以组合出 0 向量，与线性无关矛盾。故组合方法唯一。
性质3：线性基的任意一个子集异或和不为 0。其实和性质2是一样的。
标签：组合,
无关,
异或,
线性,
向量,
性质
From： https://www.cnblogs.com/buleeyes/p/17488135.html