线性基总结

线性基

(知道这玩意很久了，这次来总结一下。)

定义

基：

(在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量)(空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元)(素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量)(空间为有限维向量空间，将元素的个数称作向量空间的维数。)

线性基：

(线性基是一种特殊的基，它通常会在异或运算中出现，它的意义是：通)(过原集合S的某一个最小子集S1使得S1内元素相互异或得到的值域与原集合S相)(互异或得到的值域相同。)

[也可以说是在 mod 2的意义下，有n个长度为m的向量，这n个向量的线性基为其所组成的线性空间V的基底。 ]

三大性质

(1、原序列里面的任意一个数都可以由线性基里面的一些数异或得到。)
(2、线性基里面的任意一些数异或起来都不能得到0。)
(3、线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的。)

线性基的构造方法

(构造线性基，我们考虑用增量法来构造线性基。假如现在要插入一个向量，从左向右不断消去1，直)(到出现了第一个无法消去的1，说明这个向量无法用现在的几组基底表示出来，所以将其插入线性基。)

代码实现

ll d[65];
void addnum(ll x)
{
    for(int i=60;i>=0;i--)
    if((x>>i)&1){
        if(d[i])x^=d[i];
        else{
            d[i]=x;
            break;
        }
    }
}

性质的证明：

证明性质1

(我们知道了线性基的构造方法后，其实就可以很容易想到如何证明性质1了，我们设原序列里面有一)(个数x，我们尝试用它来构造线性基，那么会有两种结果——1、不能成功插入线性基；2、成功)(插入线性基。)

分类讨论一下

(1、不能成功插入线性基)
(什么时候不能插入进去呢？)
(显然就是它在尝试插入时异或若干个数之后变成了0。)
(那么就有如下式子：)
$$x oplus d[a] oplus d[b] oplus d[c]...=0$$
(根据上面的那个小性质，则有：)
$$d[a] oplus d[b] oplus d[c] oplus...=x$$
(所以，如果x不能成功插入线性基，一定是因为当前线性基里面的一些数异或起来可以等于x。)

(2、可以成功插入线性基)
(我们假设x插入到了线性基的第i个位置，显然，它在插入前可能异或若干个数，那么就有：)
$$x oplus d[a] oplus d[b] oplus d[c] oplus …=d[i]$$
$$ d[i] oplus d[a] oplus d[b] oplus d[c] oplus …=x$$
(所以显然，x此时也可以由线性基里面的若干个数异或得到。)

综上，性质一得证

证明性质2

由反证法：

(假设线性基中存在d[a] oplus d[b] oplus d[c]=0)
(则 d[a] oplus d[b] = d[c])
(因此d[c]根本无法插入线性基中，与假设矛盾。)
(所以性质二得证。)

性质三证明略

(推荐大佬博客：https://blog.csdn.net/a_forever_dream/article/details/83654397)

应用

(那么这玩意到底有啥用呢？)

求异或最大值

ll getmax()
{
    ll res=0;
    for(int i=60;i>=0;i--)
        if(res^d[i]>res)
            res^=d[i];
    return res;
}

求异或最小值

ll getmin()
{
    ll res=0,cnt=0;
    for(int i=60;i>=0;i--)
        if(d[i])
            cnt++,res=d[i];
    if(cnt<n)return 0;
    return res;
}

求异或第k大值

例题： https://vjudge.net/problem/HDU-3949

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+5;
ll d[65],d2[65],cnt;
void addnum(ll x)
{
    for(int i=60;i>=0;i--)
    if((x>>i)&1){
        if(d[i])x^=d[i];
        else{
            d[i]=x;
            break;
        }
        if(x==0)break;
    }
}
void change()
{
    for(int i=60;i>=0;i--)
    {
        for(int j=i-1;j>=0;j--)
        if((d[i]>>j)&1){
            d[i]^=d[j];
        }
    }
    for(int i=0;i<=60;i++){
        if(d[i])d2[cnt++]=d[i];
    }
}
int main()
{
    int _;
    scanf("%d",&_);
    for(int t=1;t<=_;t++)
    {
        memset(d,0,sizeof d);
        cnt=0;
        printf("Case #%d:
",t);
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            ll x;
            scanf("%lld",&x);
            addnum(x);
        }
        change();
        int q;
        scanf("%d",&q);
        for(int i=1;i<=q;i++){
            ll k;
            scanf("%lld",&k);
            if(n>cnt)k--;
            if(k>=(1ll<<cnt))printf("-1
");
            else{
                ll res=0;
                for(int i=0;i<cnt;i++){
                    if(1&(k>>i))res^=d2[i];
                }
                printf("%lld
",res);
            }
        }
    }
    return 0;
}