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

概述

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

定义

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

性质

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

维护（插入、合并）

插入

如果向线性基中插入数$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 ai$
如果中途$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); (0);
    int n=read();
    for(int i=1; i<=n; ++i) insert(read());
    printf("%lld\n", qmax());
}

HDU 3949 XOR(K小值)

题意：给N个数，然后求出能异或出来的第K小值
思路：求出N个数的线性基，再化简为每一个基,结果大概这个样子
$1xxxx0xxx0x$
$000001xxx0x$
$0000000001x$
然后统计有多少不为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;
            }
        }
    }    
}