线性基介绍

有一个序列AAA，若存在一个序列BBB，使得对于AAA中任意若干个数的异或和kkk，一定有BBB中的若干个数，使得这些数的异或和为kkk，且BBB是满足以上条件的长度最小的序列，则称BBB为AAA的线性基。

线性基可以用来解决一些子集异或和的问题。

线性基的性质

1. 原序列的任意一个数都可以由线性基中的若干个数的异或和得到
2. 线性基中任意若干个数的异或和不为000
3. 在保持性质1的前提下，数的个数最少

线性基的构造

设数组ddd为数组aaa的线性基（ddd从000开始），则我们可以得到ddd的长度一定小于等于aaa中的最大数的二进制的位数。为什么呢？如果di=2id_i=2^idi​=2i，则如果ddd的长度与aaa中最大数的位数，则aaa中的每一个数都能按二进制位用did_idi​异或而得。

我们规定：若did_idi​不为000，did_idi​的最高位为i+1i+1i+1。当然，did_idi​为000表示did_idi​不存在。那么，我们可以构造数组ddd。

code

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

对于每个aia_iai​，设aia_iai​的最高位为kkk，若bk−1=0b_{k-1}=0bk−1​=0，则将aia_iai​赋给bk−1b_{k-1}bk−1​，否则令ai=aia_i=a_iai​=ai​ ^ bk−1b_{k-1}bk−1​。到最后一定能有若干个数能构成后来的aia_iai​，那么用aia_iai​ ^ bk−1b_{k-1}bk−1​就能得到先前的aia_iai​

注：异或运算满足aaa ^ bbb ^ b=ab=ab=a

例题

有nnn个数组成的一个可重集合SSS，求一个集合T⊆ST\subseteq ST⊆S，使得T1⊕T2⊕T3⊕⋯⊕T∣T∣T_1 \oplus T_2 \oplus T_3 \oplus \cdots \oplus T_{|T|}T1​⊕T2​⊕T3​⊕⋯⊕T∣T∣​最大。

• n≤105n\leq 10^5n≤105
• 0≤Si≤2500\leq S_i\leq 2^{50}0≤Si​≤250

构造SSS的线性基ddd，显然SSS的最大异或和一定可以用ddd中的若干个数的异或和得到。

令答案为ansansans，ansansans的初始值为000。我们按ddd的下标从大到小遍历。对于每个did_idi​，若ans⊕di>ansans\oplus d_i>ansans⊕di​>ans，则ans=ans⊕dians=ans\oplus d_ians=ans⊕di​。为什么呢？在i+1i+1i+1位之前的的每一位不变的情况下，第i+1i+1i+1位如果是000，则将其变为111一定是更优的。因为在之后各个aia_iai​的第i+1i+1i+1位一定为000，所以只有在这个数中才能将ansansans的这一位变为111。

• 若ansansans的第i+1i+1i+1位为000，则显然ans⊕di>ansans\oplus d_i>ansans⊕di​>ans
• 若ansansans的第i+1i+1i+1位为111，则显然ans⊕di

所以我们可以通过ans⊕dians\oplus d_ians⊕di​和ansansans的大小关系来决定是否要异或did_idi​。

code

#include
using namespace std;
int n;
long long ans=0,a[100005],d[55];
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}for(int i=1;i<=n;i++){for(int j=50;j>=0;j--){if(a[i]&(1ll<if(!d[j]){d[j]=a[i];break;}a[i]^=d[j];}}}for(int i=50;i>=0;i--){if((ans^d[i])>ans) ans=ans^d[i];}printf("%lld",ans);return 0;
}