线性基汇总

kgxw0430 2019-02-25 原文

线性基

定义：

在 mod 2的意义下，有n个长度为m的向量，这n个向量的线性基为其所组成的线性空间V的基底。
构造：

我们考虑用增量法来构造线性基。假如现在要插入一个向量，从左向右不断消去1，直到出现了第一个无法消去的1，说明这个向量无法用现在的几组基底表示出来，所以将其插入线性基。（普通的线性基构造按照这样写就可以了，不过我们有一种更优秀的写法，它会有很多不错的性质）。
```
const int MAXN=31;
int a[MAXN+5];
void insert(int v){
  for(int i=MAXN;i>=0;--i) if((v>>i)&1){
      if(a[i]) v^=a[i];
      else{
          for(int j=i-1;j>=0;--j)
              if((v>>j)&1) v^=a[j];
          for(int j=i+1;j<=MAXN;++j)
              if((a[j]>>i)&1) a[j]^=v;
          a[i]=v;
          break; 
      }
  }
}
```
本质不同的子集异或和计数：

给定n个数，第i个数位\(a_i\)，询问其中有多少个本质不同的子集异或和。n\(\le10^5\)，\(a_i\le10^9\)
- 首先考虑线性基是什么？线性基是给定的n个向量通过任意变换形成的线性空间的基底，也就是说线性基任意变化形成的线性空间与之前的是完全一致的。那么就很OK了啊，我们求出线性基，如果基底数量为m，那么答案就是\(2^m\)。
最大/最小子集异或和：

给定n个数，第i个数位\(a_i\)，询问最大子集异或和与最小子集异或和。n\(\le10^5\)，\(a_i\le10^9\)
- 求最大：贪心地考虑，在二进制下，高位为1一定更优。所以我们从左向右（即从高位向低位）选，如果当前值xor当前基底之后答案变大，就xor。最后得到的一定是最大值。
- 求最小：不要陷入最大的闭合思路里面。求最小值涉及到了用了上面构造方法构造出来的线性基的性质。（1）如果在插入一个数的时候，发现这个数无法被插入线性基，说明已经可以变换出这个数了，那么最小值一定为0。（2）如果没有第一种情况，那么最小值一定是线性基里最小的数。
异或和为零的子集计数：

给定n个数，第i个数位\(a_i\)，询问有多少个子集是满足异或和为零的。n\(\le10^5\)，\(a_i\le10^9\)
- 考虑假如一个向量无法插入线性基，那么在线性基内一定有一个子集异或和等价于它，所以会形成一个异或和为0的子集。一般的，线性基外的所有向量，任意组合的子集形成的向量一定在线性基内可以体现，所以异或和为0的子集个数应该是\(2^k\)，k为线性基外的向量数。