线性基¶

概念¶

线性基是指在数学中，尤其是在线性代数领域，一个由一组向量组成的集合，这些向量的点积为1，且任何其他向量都可以表示为这个集合中向量的线性组合。

简单来说，线性基就是一个向量空间的一组基本向量，这些向量在一起构成了整个空间的基底。

异或线性基¶

异或线性基: 一个数列 A，P 是一组异或线性基，则：

P 中任意非空子集的异或和不为0
P 中数的最高位1不重复
P 中数的个数≤A中数的个数
A中任意数字都能通过P中的一些数字异或出来

异或线性基的构造方法：贪心法和高斯消元法因为高斯消元法构造的异或线性基有更好的性质，能更加方便地解决问题。

例题 #1【模板】线性基¶

给定 \(n\) 个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。

\(1 \leq n \leq 50, 0 \leq S_i < 2 ^ {50}\)

实际上线性基的时间复杂度为O(63n)，n可以是\(10^5\)。

思路: 1.先构造出的n个整数的异或线性基 2.n个整数的子集的最大异或和等于其线性基的最大异或和 3.直接将线性基中所有元素都异或起来即是答案

这里的线性基表示：取这些线性基中的任意个元素的异或和，可以得到集合中的每一个元素。并且线性基之间不可互相表示（这是基的概念了）。

高斯消元法¶

/*
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'

*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first
#define ull unsigned long long

#define itn int
// #define inr int
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    if(1)cerr<<' ';
    cerr << s;
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

int cnt;
int n;
int a[N];

void gauss(){
    for(int i=62;~i;i--){
        for(int j=cnt;j<n;j++){
            if(a[j]>>i&1){
                swap(a[j],a[cnt]);
                break;
            }
        }

        if(!(a[cnt]>>i&1))continue;

        for(int j=0;j<n;j++){
            if(j!=cnt&&(a[j]>>i&1))a[j]^=a[cnt];
        }
        cnt++;
        if(cnt==n)break;

    }

}

void solve(){
    n=rd;
    for(int i=0;i<n;i++){
        a[i]=rd;
    }

    gauss();


    int ans=0;
    for(int i=0;i<cnt;i++){
        ans^=a[i];
    }

    cout<<ans<<endl;
}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".in","w",stdout);

    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

贪心法¶

贪心法构造的线性基可能会有高位重复的情况（即\(p_i\)的最高位在\(p_j\)中也为1，但是仍然保证没有两个p的最高位相同）。因此在取异或和最大值时要从大到小枚举线性基并贪心地与ans异或。

/*
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'

*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first
#define ull unsigned long long

#define itn int
// #define inr int
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    if(1)cerr<<' ';
    cerr << s;
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

int cnt;
int n;
int p[N];

void insert(int x){
    for(int i=63;~i;i--){
        if(x>>i&1){
            if(p[i])x^=p[i];
            else {
                p[i]=x;
                break;
            }
        }
    }
}
void solve(){
    n=rd;
    for(int i=0;i<n;i++){
        insert(rd);
    }

    int ans=0;
    for(int i=63;~i;i--){
//      cdbg(p[i]);
        if((ans^p[i])>ans)ans^=p[i];//注意优先级
    }

    cout<<ans<<endl;
}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".in","w",stdout);

    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

/*
4
6 5 9 10
*/