线性基专题总结

莫(tui)名(wan)其(ti)妙(jie)又弄完了一个专题？

刚开始以为这个知识点出题都是板子来着，后来做题才发现我太天真了啊

先列知识点吧

• 1.性质
  (1).  原序列异或能得到的所有数都可以由线性基中的一些数异或得到
  (2). 线性基里面的任意一些数异或起来都不能得到 \(0\)
  (3). 线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的
  (4). 若线性基中有k个元素，则原序列异或能得到的数一共有 \(2^k\) 种，每种有 \(2^{n-k}\) 个
  (5). 线性基中元素互相异或，异或集合不变

 

• 2.构造
  从高到低扫描线性基中的每一位
  如果这一位没有值但是 \(x\) 的这一位有值，则令线性基这一为 \(x\)
  否则令 \(x=x \ xor\ b[i]\)
    放个代码

inline bool insert(ll x){
    for(int i=63;i>=0;i--){
        if(x&(1ll<<i)){
            if(!d[i]){
                d[i]=x;
                return 1;
            }
            else x^=d[i];
        }
    }
    return 0;
}

 

• 3.使用

 

 

 

 

• 4.题解包