线性基

一、概念

在线性代数中，对于向量组$\alpha_1,\alpha_2,\dots,\alpha_n$，我们把其张成空间的一组线性无关的基成为该向量组的线性基。

二进制集合$S=\lbrace { x_1,x_2,\dots,x_n\rbrace }$，得到另一个二进制集合$S'=\lbrace { y_1,y_2,\dots y_n\rbrace }$，保证在S中任取子集$A$，都能在$S'$中找到对应的子集$A'$，使得$A$与$A'$的异或和相等；同时$S'$中任意一个元素都不能被$S'$中其他元素的组合异或出来。我们把$S'$称为$S$的线性基，利用它可以方便的求出原集合的k大异或和。
（来自我喜欢的知乎博主Pecco）

二、理解

对概念有一定初级的了解之后，我想说一下我的理解：
1）关于线性基：线性基就好比一堆向量（数），可以用若干个线性基里面的来表示一个集合里面的所有数，他们互相线性无关。
2）关于线性无关：就是线性代数里面的，线性基里面的每个数都有贡献，原集合里面的数只能在线性基里面找一组唯一的子集来通过异或和来表示。
3）总的来看，就好比我们高中学过的多维向量，我们可以用一组基底来表示原来所有的向量，而且唯一。

三、构造

线性基的构造一般由两种方法，一种是用数组来，一种是用vector的简单方法，我看大部分的题目还是用的前者，所以建议还是用前者。

3.1数组

3.1.1理解p数组

我们这里是有一个p数组，对于一般的1e18数据，我们开最多循环62位，所以p数组开到65、100就行了。
p[i]代表的是最高有效位为第i位的线性基的向量，怎么理解呢，比如我们插入x=01001101，那么我们会判断x&(1<<i)时候(此时i=6)时候有效，将p[6]=01001101，因为最高有效位为第六位（这里包括第0位），大致懂了吧，也就是说，我们线性基最多有62位（63个，包括第0位），我这个时候其中有一个是01001101

3.1.2理解动态和构造

为什么说动态呢，因为我们线性基是会变的，举一个简单的例子，如果这时候原集合为$S=\lbrace {01001101,01101001\rbrace }$，那么我们此时将x=01101001插入进来，再线性基的判断的时候（从高往低），我们会将判断到最高位到第六位的时候，此时p[6]已经有值了，所以我们将x进行异或操作，通过x^=p[i]，将x更新为x=00100100，此时我们继续循环x的最高有效位，到第五位的时候，我们会判断到p[5]此时没有数，所以我们将x赋值给p[5]，此时p[5]=00100100

我们再来看线性基，里面已经有两个基了，分别是p[6]=01001101和p[5]=01001101，线性基里面的数时能够通过若干个来异或和来表示原集合里面的所有数，比如原集合的第一个数a[1]=01001101，我们会发现就是p[6]可以表示，那第二个数a[2]=01101001呢，通过构造我们可以发现这个p[5]是由于p[5]=a[2]^a[6]而来的，所以式子两边同时异或a[6]就可以得到a[2] = p[5] ^ p[6]，我们用到了以下的两个异或性质
1）a ^ b =c --> a = c ^ b
2）(a ^ b) ^ b = a

所以我们的线性基是动态的，一直是变化的。

3.1.3过程

好了，理解了前面两个了，我们的过程就很容易出来了。
1）每次读入一个x，就进行插入操作，操作包括对线性基的更新和插入线性基，或者无操作（可以被表示）。
2）如果我们找到了

inline bool insert(ll x)
{
    for (int i=62;i>=0;i--)
        if (x>>i)//为什么可以不写x&(1<<i)?，因为我们每次x的最高位都是因为x^=p[i]变为0，这样也能判断最高位
            if (p[i])
                x^=p[i];//如果第i位这个线性基有，同上方的p[6]
            else
            {
                p[i]=x;
                return 1;//1代表插入成功
            }
    return 0; //0代表这个数x能被线性基表示，0需要特判
}

3.2.vector

3.2.1代码

vector<ull> B;
void insert(ull x) {
    for (auto b : B)
        x = min(x, b ^ x);//与之前方法一样，对于已经存在的线性基进行异或，不断减少x
    for (auto &b : B)
        b = min(b, b ^ x);//修改原来的
    if (x)//如果x还有，说明整个线性基不能表示出
        B.push_back(x);//x就是新的线性基
}

3.2.2理解

其实方法类似，之前的线性基用p[65]来保存，这里用vector容器来保存，我们对于新来的一个数x，让他对每一个线性基都异或一边，保存最小的x下来。

再对线性基每一个都进行更新，这样保证线性基里面都是最小的。

最后如果x还有剩下的，说明x不能被表示，那么还需要什么才能表示原数呢？不难理解，还需要剩下的x来表示原数。

3.3注意特判是否有0

如果最后x没有了，也就代表在之前遍历所有的线性基异或出来的结果为0，说明原数是能够被若干个线性基里面的向量来表示，所以0是可以被异或出来的，注意这句话，在以后的k大异或和有重要作用

四.补充与实现

4.1插入(insert)

就如同上方的代码，不过多介绍。

inline void insert(ll x)
{
    for (int i=62;i>=0;i--)
        if (x>>i)
            if (p[i])
                x^=p[i];
            else
            {
                p[i]=x;
                return;
            }
    flag=1;//这样标记也可以，看是否有没有0，代表这个数能否被异或出来
}

4.2重构(rebuild)

重构？什么时候需要重构，这里重构指的是求k大异或和的时候。

这里讲一个结论，假如我们在构造的时候没有x=0也就是每一次都插入成功，对于插入的每一个数不能由线性基里面的若干个向量表示，换句话说，这个时候线性基里面若干个向量无法异或和为0.

好，在这个前提上，其实有没有0就是多了一位而已，比如我们求k大异或和的时候，只需要将k转化为二进制，比如说我们要求第5大异或和，那么我们转换成二进制$5_{10}=101_2$，我们只需要将d[0]^d[2]即可，这里的d[i]是什么？

在第一种数组存储的方法里，d[i]代表的是线性基的里面的向量，并且从小到大按照顺序存储，并且向量是最小的，比如上述样例里面的p[6]与p[5]，这个时候d[0]=p[5],d[1]=p[6];

在第二种vector存储的方法里面，d[i]实际上就是我们的vector顺序B[i]

这个时候用数组存储的话分为两步：
1）将线性基里面的向量变为最小
2）将p[i]从低到高存入d[i]中

inline void rebuild()
{
    for (int i=0;i<=62;i++)//从低到高
        for (int j=i-1;j>=0;j--)//看到比i小的，更新
            if (p[i]&(1ll<<j))//如果p[i]的第j位为1，那么就异或成0
            //因为此时如果p[j]=0的话1^0=1不变
            //如果此时p[j]是存有一个向量的话，就能把这一位的数字异或成0，1^1=0，达到减小的目的
                p[i]^=p[j];
    for (int i=0;i<=62;i++)
        if (p[i]) 
            d[cnt++]=p[i];//存入d数组
}

4.3询问k大异或和

上面说过了一个结论，如果我们要求k大，首先只需要判断一下是否由0特殊存在，然后将其进行二进制分解，上述讲的比较清楚了。

inline ll ask_kth(ll x)
{
    if (x>=(1ll<<cnt)) return -1;//越界，不存在
    ll res=0;
    for (int i=0;i<=62;i++)
        if (x&(1ll<<i)) res^=d[i];//二进制分解
    return res;
}

4.4特判0的存在

为什么说要特判0的存在呢，假如原集合有的数字是能够被线性基异或表示出来的，说明0存在了，那么我们求k大异或和的时候，0一定是最小的，但是我们直接将ask_kth(1)的时候会进行二进制分解，然后res=res^d[0]，返回的是d[0]也就肯定不是0，此时d[0]表示的实际上是2大异或和.

假如我们有0的存在，在求K大异或和的时候，我们实际上是求ask_kth(k-1)；为什么？因为实际上是k大疑惑和我，除去0之后是k-1大异或和，我们的ask_kth(k)函数是不包括0的。

五、题目链接

模板题链接

LOJ113.最大异或和
LOJ114.K大异或和
BJWC2011元素
BJWC2011元素题解

模板题代码

最大异或和

inline void insert(ll x)
{
    for (int i=62;i>=0;i--)
        if (x>>i)
            if (p[i])
                x^=p[i];
            else
            {
                p[i]=x;
                return;
            }
}
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        insert(x);
    }
    for (int i=62;i>=0;i--)
        if ((ans^p[i])>ans) ans=ans^p[i];
    cout<<ans;
}

k大异或和

inline void insert(ll x)
{
    for (int i=62;i>=0;i--)
        if (x>>i)
            if (p[i])
                x^=p[i];
            else
            {
                p[i]=x;
                return;
            }
    flag=1;
}
inline void rebuild()
{
    for (int i=0;i<=62;i++)
        for (int j=i-1;j>=0;j--)
            if (p[i]&(1ll<<j))
                p[i]^=p[j];
    for (int i=0;i<=62;i++)
        if (p[i]) 
            d[cnt++]=p[i];
}
inline ll ask_kth(ll x)
{
    if (x>=(1ll<<cnt)) return -1;
    ll res=0;
    for (int i=0;i<=62;i++)
        if (x&(1ll<<i)) res^=d[i];
    return res;
}
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        insert(x);
    }

    rebuild();
    cin>>m;
    while (m--)
    {
        cin>>x;
        if (flag&&x==1)
            cout<<0<<endl;
        else 
            if (!flag) cout<<ask_kth(x)<<endl;
            else cout<<ask_kth(x-1)<<endl;

    }
}

六、总结

线性基主要理解以下几个方面：
1）线性无关
2）k大异或和结论
3）两种构造
4）特判0