我们用高斯消元的方法来弄线性基。
首先，对于aiai，我们从高位到低位查看每一位，如果当前位数是1，那么就查看高斯消元矩阵的第jj行，假如jj行jj列是1，就将aiai每一位异或与第jj行每一位做异或，继续处理。否则将ai放置在第jj行，然后消元即可。
代码如下。
int n;
scanf("%d",&n);
ll x;
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
for(int j=60;j>=0;j--)
{
if(x>>j&1)
{
if(a[j])x^=a[j];
else
{
a[j]=x;
break;
/*或者
num++;
a[j]=x;
for(int k=j-1;k>=0;k--)if(a[k]&&(a[j]&bin[k]))a[j]^=a[k];
for(int k=j+1;k<=60;k++)if(a[k]&bin[j])a[k]^=a[j];
break;
*/
}
}
}
}
https://www.luogu.com.cn/problem/P3812
#include <stdio.h>
#define ll long long
ll a[55];
int main()
{
int n;
scanf("%d",&n);
ll x;
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
for(int j=60;j>=0;j--)
{
if(x>>j&1)
{
if(a[j])x^=a[j];
else
{
a[j]=x;
break;
}
}
}
}
ll ans=0;
for(int i=60;i>=0;i--) //从大往小，大的优先级比小高
if((ans^a[i])>ans)ans^=a[i];
printf("%lld",ans);
}
https://vjudge.net/problem/HDU-3949
#include <stdio.h>
#include <string.h>
#define ll long long
ll a[61],b[61],bin[61];
int hav0,cnt;
int n;
void init()
{
memset(a,0,sizeof(a));
ll x;
int num=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
for(int j=60;j>=0;j--)
{
if(x&bin[j])
{
if(a[j])x^=a[j];
else
{
num++;
a[j]=x;
for(int k=j-1;k>=0;k--)if(a[k]&&(a[j]&bin[k]))a[j]^=a[k];
for(int k=j+1;k<=60;k++)if(a[k]&bin[j])a[k]^=a[j];
break;
}
}
}
}
hav0=(num!=n),cnt=0;
for(int i=0;i<=60;i++)if(a[i])b[cnt++]=a[i];
}
ll query(int k)
{
k-=hav0; //有无零向量
if(k>=bin[cnt])return -1; //超出范围
ll ans=0;
for(int i=0;i<cnt;i++)if(k&bin[i])ans^=b[i]; //二进制思想
return ans;
}
int main()
{
int t,m,k;
scanf("%d",&t);
bin[0]=1;for(int i=1;i<=60;i++)bin[i]=bin[i-1]*2;
for(int i=1;i<=t;i++)
{
printf("Case #%d:\n",i);
scanf("%d",&n);
init();
scanf("%d",&m);
while(m--)
{
scanf("%d",&k);
printf("%lld\n",query(k));
}
}
}