线性基学习总结

https://ac.nowcoder.com/acm/contest/884/B

这道题是第一次遇到线性基相关的题目，解法是线性基求交+线段树。

在解决这道题的过程中，我恶补了一波线性基相关的知识。

一、认识线性基

1.什么是线性基

　　通过原集合S的某一个最小子集S1使得S1内元素相互异或得到的值域与原集合S相互异或得到的值域相同。这个S1就是原集合S的线性基。

2.线性基的性质

线性基能相互异或得到原集合的所有相互异或得到的值。
线性基是满足性质1的最小的集合
线性基没有异或和为0的子集。

3.作用

　　通过线性基的定义和性质，我们知道，一般线性基都用来解决一个集合中xor的最大值，最小值，第k小值，或者多个集合xor值域的求交，求并。

二、写法

1.构造线性基

LL b[70]; 

int add(LL x)   //将x插入线性基中 
{
    for(int i=63;i>=0;i--) 
    {
        if(!(x>>(LL)i)) continue;    //找到x最高的为1的二进制位 i 
        if(!b[i])   //如果当前b[i]为空，则插入线性基 
        {
            b[i]=x;
            tot++;    //tot表示线性基里不为0的元素的个数 
            return 1;   //插入成功 
        }
        else x^=b[i];   //如果b[i]不为空，则将x异或上b[i]继续查找 
    }
    return 0;  //插入x失败 
}

2.求集合的最大异或和

　　例题：https://www.luogu.org/problem/P3812

　　首先我们有了一个集合的线性基，最大异或和就贪心的取使最终答案可以增大的值异或就行了。

LL ans=0;
for(int i=63;i>=0;i--) if(ans<(ans^b[i])) ans^=b[i];

3.求集合的最小异或和

　　答案是很显然的，如果集合能异或为0，则答案为0，如果不能，就是最小的b[i]。

4.求集合的第k小异或和

　　例题：http://acm.hdu.edu.cn/showproblem.php?pid=3949

　　首先我们将原本的线性基处理成如下的形式：

　　1xxxx0xxx0x
1xxx0x
1x

　　处理方法：

for(int i=1;i<=63;i++)
    for(int j=0;j<i;j++)
        if(b[i]&(1<<j)) b[i]^=b[j];

　　答案初始值设为0，然后将看k的二进制数，如果某一位为1，ans异或上线性基中的这一位的数，注意这个线性基是处理后的线性基，其中为0的位已经被忽略。

LL ans=0;
for(int j=0;j<=63;j++)
{
    if(b[j])
    {
        if(k&1) ans^=b[j];
        k>>=1;
    }
}
printf("%lld
",ans);

5.两线性基合并

　　这个太简单，把线性基A中的元素依次向线性基B中插入，最后B就是合并后的线性基了

6.两线性基求交

　　例题：https://ac.nowcoder.com/acm/contest/884/B

　　在线性基A与B中，取Bi，如果Bi能由A中的某些数和Bi+1到Bm中的某些数异或得到，即A[a1]^A[a2]^...^A[an]^B[b1]^B[b2]^...^B[bn]=B[i]，即B[i]^A[a1]^A[a2]^...^A[an]^B[b1]^B[b2]^...^B[bn]=0，其中a=[1,n],b=[i+1,n]，那么可知A[a1]^A[a2]^...^A[an]=B[i]^B[b1]^B[b2]^...^B[bn]=C[i]，C[i]即我们要向答案中插入的一位。那么我们将A[a1]^A[a2]^...^A[an]加入答案线性基。

LB Merge(LB A,LB B)
{
    LB All=A,C,D;    //C为答案线性基，D记录All中每一位都由A中哪些位异或出的 
    C.clear();D.clear();    //记住要初始化 
    for(int i=63;i>=0;i--) D.b[i]=1ll<<i;
    for(int i=63;i>=0;i--)
    {
        if(B.b[i])
        {
            bool can=true;
            LL v=B.b[i],k=0;
            for(int j=63;j>=0;j--)
            {
                if(!(v>>j)) continue;
                if(!All.b[j])     //如果当前B[i]不能由All中的数异或得到，则插入 
                {
                    can=false;    //当前v不是答案 
                    All.b[j]=v;
                    D.b[j]=k;
                    break;
                }
                else
                {
                    v^=All.b[j];
                    k^=D.b[j];
                }
            }
            if(can)             //如果v最终等于0 
            {
                for(int j=63;j>=0;j--)
                {
                    if(k&(1ll<<j)) v^=A.b[j];  //将A[a1]^A[a2]^...^A[an]加入答案线性基 
                }
                C.add(v);
            }
        }
    }
    return C;
}