线性基学习笔记

lizhous · 2022-11-21 21:00:34 · 个人记录

概念

• 线性基是一个集合。
• 从原集合中选取任意数都能通过线性基中的数异或得到。

本质上是对集合的压缩

性质

1. 所有数字没有最高位相同的

2. 集合大小为 \log_2 级别。

操作

排查：若线性基内有最高位相等的，让其相异或，并继续排查直到没有可操作的数。

若原集合内有 0 线性基无法实现。

实现

void insert(int x)
{
    for(int i=62;i>=0;i--)
   {
        if(x&(1ll<<i))
       {
            if(xxj[i])
           {
                x^=xxj[i];
           }
           else
           {
                xxj[i]=x;
               return;
           }
       }
   }
   return ;
}