算法分享

写一些关于线性基的理解
1：线性基的性质
（1）原序列里面的任意一个数都可以由线性基里面的一些数异或得到
（2）线性基里面的任意一些数异或起来都不能得到 0
（3）线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的
2：线性基的应用以及使用办法
（1）可以判断一个数字是否可以被一个序列的子集异或得到
（2）求序列的异或最大值，最小值，第k大值

应用1

C++ 代码

//我们尝试往线性基里插入这个数
//如果可以插入进去则代表他是不能被已有的子集异或出来的
//反之则可以被异或出来
//简单证明一下是这样的假设插进来一个数字x
//如果插入不进去，一定是被从大到小异或为0了
//则有a[i]^a[j]^a[k]...^x==0
//那么对式子进行移项
//    a[i]^a[j]^a[k]...==x

应用2

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=5e5+10;

const int B=60;
struct linear_basis
{
    int num[B+1];
    bool insert(int x)
    {
        for(int i=B-1;i>=0;i--)
        {
            if(x&(1ll<<i))
            {
                if(num[i]==0){num[i]=x;return true;}
                x^=num[i];
            }
        }
        return false;
    }
    int makemax(int x)
    {
        int ans=x;
        for(int i=B-1;i>=0;i--)
        {
            ans=max(ans,ans^num[i]);
        }
        return ans;
    }
    int makemin(int x)
    {
        int ans=x;
        for(int i=B-1;i>=0;i--)
        {
            ans=min(ans,ans^num[i]);
        }
        return ans;
    }
}T;

signed main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    int l=0;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        if(!T.insert(x))l++;
    }
    k/=(1ll<<l);
    vector<int>q;
    for(int i=0;i<=B-1;i++)
    {
        if(T.num[i]!=0)
        {
            q.push_back(T.num[i]);
        }
    }
    int x=q.size();
    int ans=0;
    for(int i = x - 1;i >= 0;i --)
    {
        if(k & ( 1ll << i))
        {
            ans=max(ans,ans^q[i]);
        }
        else ans=min(ans,ans^q[i]);
    }
    cout<<ans<<endl;
    return 0;
}