线性基(线性无关的基底)

概述

所谓线性基，就是线性代数里面的概念。一组线性无关的向量便可以作为一组基底，张起一个线性的向量空间，这个基底又称之为线性基。这个线性基的基底进行线性运算，可以表示向量空间内的所有向量，也即所有向量可以拆成基底的线性组合。

定义

设数集 $T$ 的值域范围为 $[1, 2^{n} - 1]$ 。
$T$ 的线性基是 $T$ 的一个子集 $A =$ { $a 1, a 2, a 3, . . ., a n$ }。
$A$ 中元素互相 $x o r$ 所形成的异或集合，等价于原数集 $T$ 的元素互相 $x o r$ 形成的异或集合。
可以理解为将原数集进行了压缩。

性质

设线性基的异或集合中不存在 $0$ 。
线性基的异或集合中每个元素的异或方案唯一，其实这个跟性质1是等价的。
线性基二进制最高位互不相同。
如果线性基是满的，它的异或集合为 $[1, 2^{n} - 1]$ 。
线性基中元素互相异或，异或集合不变。

维护（插入、合并）

插入

如果向线性基中插入数 $x$ ，从高位到低位扫描它为 $1$ 的二进制位。
扫描到第 $i$ 时，如果 $a_{i}$ 不存在，就令 $a_{i} = x$ ，否则 $x = x \otimes a_{i}$ 。
$x$ 的结局是，要么被扔进线性基，要么经过一系列操作过后，变成了 $0$ 。

bool insert(ll val) {
    for(int i=62; i>=0; i--) if(val>>i)) {
        if (!a[i]) { a[i]=val; break; }
        val^=a[i];
    }
    return val>0;
}

合并

将一个线性基暴力插入另一个线性基即可。

查询（存在性、最大值、最小值、K小值）

存在性

如果要查询 $x$ 是否存于异或集合中。
从高位到低位扫描 $x$ 的为 $1$ 的二进制位。
扫描到第 $i$ 位的时候 $x = x \otimes a i$
如果中途 $x$ 变为了 $0$ ，那么表示 $x$ 存于线性基的异或集合中。

最大值

从高位到低位扫描线性基。
如果异或后可以使得答案变大，就异或到答案中去。

ll qmax() {
    ll ans=0;
    for(int i=62; i>=0; --i)
        if((ans^p[i])>ans) ans^=p[i];
    return ans;
}

最小值

最小值即为最低位上的线性基。(就是最小的那一个)

ll qmin() {
    for(int i=0; i<=62; i++) if(d[i]) return d[i];
    return 0;
}

K小值

根据性质 $3$ 。
我们要将线性基改造成每一位相互独立。
具体操作就是如果 $i < j$ ， $a_{j}$ 的第 $i$ 位是 $1$ ，就将 $a_{j}$ 异或上 $a_{i}$ 。
经过一系列操作之后，对于二进制的某一位 $i$ 而言，只有 $a_{i}$ 的这一位是 $1$ ，其他的这一位都是 $0$ 。
所以查询的时候将 $k$ 二进制拆分，对于 $1$ 的位，就异或上对应的线性基。
最终得出的答案就是 $k$ 小值。

void rebuild() {
    for(int i=62; i; --i)
        for(int j=i-1; j>=0; --j) if(a[i]>>j) a[i]^=a[j];
    for(int i=0; i<=62; i++) if(a[i]) p[cnt++]=a[i];
}

ll qkmin(ll k) {
    ll ans=0;
    if(k>=(1ll<<cnt)) return -1;
    for(int i=cnt-1; i>=0; i--)
        if(k&(1ll<<i)) ans^=p[i];
    return ans;
}

先推荐一个

再推荐一个

最大值板子题

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline ll read() {ll x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

ll p[63], a[63], cnt;

void insert(ll a) {
    for(int i=62; i>=0; --i) if(a>>i&1) {
        if(!p[i]) { p[i]=a; break; }
        a^=p[i];
    }
}

ll qmax() {
    ll ans=0;
    for(int i=62; i>=0; --i)
        if((ans^p[i])>ans) ans^=p[i];
    return ans;
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    int n=read();
    for(int i=1; i<=n; ++i) insert(read());
    printf("%lld\n", qmax());
}

HDU 3949 XOR(K小值)

题意：给N个数，然后求出能异或出来的第K小值
思路：求出N个数的线性基，再化简为每一个基,结果大概这个样子
$1 x x x x 0 x x x 0 x$
$000001 x x x 0 x$
$0000000001 x$
然后统计有多少不为0的基，数量为tot
如果N!=tot，说明可以组成0（单纯用线性基不行）
如果K>=1<<tot，说明不存在第K小的值
最后利用线性基按照K进行构造，得到第K小的值。

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

const int maxn = 1e4+10;

int N, Q;
ll K, a[maxn], b[66], tot;

void Gauss() {
    memset(b,0,sizeof(b));
    for(int i=0; i<N; ++i) {
        for(int j=63; j>=0; --j) {
            if((a[i]>>j)&1) {
                if(b[j]) a[i]^=b[j];
                else {
                    b[j]=a[i];
                    break;
                }
            }
        }
    }
    for(int i=63; i>=0; --i) {
        if(!b[i]) continue;
        for(int j=i+1; j<63; ++j) {
            if((b[j]>>i)&1) b[j]^=b[i];
        }
    }
    tot=0;
    for(int i=0; i<=63; ++i) if(b[i]) b[tot++]=b[i];
}

int main() {
    ios::sync_with_stdio(false);
    int T, t=0;
    cin>>T;
    while(T--) {
        cout<<"Case #"<<++t<<":"<<endl;
        cin>>N;
        for(int i=0; i<N; ++i) cin>>a[i];
        Gauss();
        cin>>Q;
        while(Q--) {
            cin>>K;
            if(N!=tot) K--;
            if(K>=(1ll<<tot)) cout<<-1<<endl;
            else {
                ll ans=0;
                for(int i=0; i<tot; ++i) if((K>>i)&1) ans^=b[i];
                cout<<ans<<endl;
            }
        }
    }    
}