题解 P3812 【【模板】线性基】

· · 题解

线性基简介

线性基是一种擅长处理异或问题的数据结构.设值域为[1,N]，就可以用一个长度为\lceil \log_2N \rceil的数组来描述一个线性基。特别地，线性基第i位上的数二进制下最高位也为第i位。

一个线性基满足，对于它所表示的所有数的集合S，S中任意多个数异或所得的结果均能表示为线性基中的元素互相异或的结果，即意，线性基能使用异或运算来表示原数集使用异或运算能表示的所有数。运用这个性质，我们可以极大地缩小异或操作所需的查询次数。

插入和判断

我们考虑插入的操作，令插入的数为x，考虑x的二进制最高位i，

如果退出时x=0，则此时线性基已经可以表示原先的x了；反之，则说明为了表示x，往线性基中加入了一个新元素。

很容易证明这样复杂度为\log_2x，也可以用这种方法判断能否通过原数列异或得到一个数x。

void ins(ll x){
    for(reg int i=MN;~i;i--)
        if(x&(1ll<<i))
            if(!a[i]){a[i]=x;return;}
            else x^=a[i];
    flag=true;
}
bool check(ll x){
    for(reg int i=MN;~i;i--)
        if(x&(1ll<<i))
            if(!a[i])return false;
            else x^=a[i];
    return true;
}

查询异或最值

查询最小值相对比较简单。考虑插入的过程，因为每一次跳转操作，x的二进制最高位必定单调降低，所以不可能插入两个二进制最高位相同的数。而此时，线性基中最小值异或上其他数，必定会增大。所以，直接输出线性基中的最小值即可。

考虑异或最大值，从高到低遍历线性基，考虑到第i位时，如果当前的答案x第i位为0，就将x异或上a_i；否则不做任何操作。显然，每次操作后答案不会变劣，最终的x即为答案。

同样，我们考虑对于一个数x，它与原数列中的数异或的最值如何获得。用与序列异或最大值类似的贪心即可解决。

查询k小值

我们考虑进一步简化线性基。显然，一个线性基肯定可以表示为若干个形如2^i的数。从高到低处理线性基每一位，对于每一位向后扫，如果当前数第i位为0，且线性基第i位不为0,则将当前数异或上a_i。这一操作可以在O(\log_2^2 n)的时间内解决。

经过这一步操作后，设线性基内共有cnt个数，则它们共可以表示出2^{cnt}个数。当然，对于0必须特殊考虑。如果插入的总数n与cnt相等，就无法表示0了。

同样，考虑最小值时，也必须要考虑到0的情况。事实上，如果插入时出现了未被加入的元素，就肯定可以表示出0。

随后，我们考虑将k二进制拆分，用与快速幂类似的方法就可以求出第k大值。

学过线性代数的同学应该可以看出，这个过程就是对一个矩阵求解异或意义下的秩的过程。因此，cnt \leq \lceil \log_2N \rceil一定成立。而最终，线性基中保存的也是异或意义下的一组极小线性无关组。

同样，有关线性基的一切运算都可以看做矩阵的初等行列变换，也就可以将其看做线性规划问题。同样，可以离线使用高斯消元来构造极小线性基。

bool flag;//可以表示0
ll qmax(ll res=0){
    for(reg int i=MN;~i;i--)
        res=max(res,res^a[i]);
    return res;
}
ll qmin(ll res=0){
    if(flag)return 0;
    for(reg int i=0;i<=MN;i++)
        if(a[i])return a[i];
}
ll query(ll k){
    reg ll res=0;reg int cnt=0;
    k-=flag;if(!k)return 0;
    for(reg int i=0;i<=MN;i++){
        for(int j=i-1;~j;j--)
            if(a[i]&(1ll<<j))a[i]^=a[j];
        if(a[i])tmp[cnt++]=a[i];
    }
    if(k>=(1ll<<cnt))return -1;
    for(reg int i=0;i<cnt;i++)
        if(k&(1ll<<i))res^=tmp[i];
    return res;
}

代码

#include<bits/stdc++.h>
#define reg register
using namespace std;
typedef long long ll;
const int MN=60;
ll a[61],tmp[61];
bool flag;
void ins(ll x){
    for(reg int i=MN;~i;i--)
        if(x&(1ll<<i))
            if(!a[i]){a[i]=x;return;}
            else x^=a[i];
    flag=true;
}
bool check(ll x){
    for(reg int i=MN;~i;i--)
        if(x&(1ll<<i))
            if(!a[i])return false;
            else x^=a[i];
    return true;
}
ll qmax(ll res=0){
    for(reg int i=MN;~i;i--)
        res=max(res,res^a[i]);
    return res;
}
ll qmin(){
    if(flag)return 0;
    for(reg int i=0;i<=MN;i++)
        if(a[i])return a[i];
}
ll query(ll k){
    reg ll res=0;reg int cnt=0;
    k-=flag;if(!k)return 0;
    for(reg int i=0;i<=MN;i++){
        for(int j=i-1;~j;j--)
            if(a[i]&(1ll<<j))a[i]^=a[j];
        if(a[i])tmp[cnt++]=a[i];
    }
    if(k>=(1ll<<cnt))return -1;
    for(reg int i=0;i<cnt;i++)
        if(k&(1ll<<i))res^=tmp[i];
    return res;
}
int main(){
    int n;ll x;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&x),ins(x);
    printf("%lld\n",qmax());
    return 0;
}