我眼中的通俗易懂的线性基

线性基

我在学这个的时候不明白基是一个什么东西，然后我想了很久没法理解究竟什么叫做线性基，千万不要理解成是一个序列选一些数使之异或和最大。。

首先
你得有一些高一数学基础比如说向量，我们可以任意定义两条单位长度的向量，这两条能够成该平面直角坐标系的所有向量，这两条向量称之为基底。
那么，线性基差不多也是这个意思，

线性基的定义

：
（百度百科）

通过原集合S的某一个最小子集S1使得S1内元素相互异或得到的值域与原集合S相互异或得到的值域相同。

emm怎么说呢，线性基能够成这个序列所能产生的任何xor值，即线性基
类似于基底对于平面直角坐标系的基底

为什么呢？首先我们要明白xor的一个性质
^即xor的运算符
1.
a

a

$a$^b=b

$b=b$

$b=b$^
a

a

$a$
2.如果
a

$a$

$a$^
b=c

b

=

c

$b=c$
那么

a

a

$a$^c=b

$c=b$

$c=b$

c

c

$c$^b=a

$b=a$

$b=a$

根绝这两个性质，我们可以由任意一组下面的
s[i]

s

[

i

]

$s[i]$来得到其他的数
我这里用一个s数组来维护线性基

s[x]

s

[

x

]

$s[x]$代表
x

x

$x$位是1，且x

$x$

$x$位是该数的最高位。
类似于反着来的
lowbit(x)

l

o

w

b

i

t

(

x

)

$lowbit(x)$(树状数组)

我们可以来模拟一组数据

先上代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=1e6+5;
const int mod=1e9+7;
ll a[maxn],sum,s[65];
void insert(ll val)
{
    for(int i=60;i>=0;i--)
      if (val&(1ll<<i))
        if (!s[i])
          {
            s[i]=val;
            return;
          }
        else val^=s[i];
}
int main()
{
    ll n,j,k;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
      insert(a[i]);
    ll ans=0;
    for (int i=60; i>=0; i--)
      if ((ans^s[i])>ans) ans^=s[i];
    printf("%lld\n",ans);
    return 0;
}