题目描述：
他得到了一个长度为 n 的数组 a1,a2,a3,...,an，他想知道 xor 值为 0 的子 序列最长是多少。
标签：线性基，FWT
思路：
我们要找异或值为0的，可以反过来寻找异或值为整个数组异或值的数。我们知道一个序列的线性基为权值位数，即至多为log个。
所以我们可以知道异或值为总异或值的个数的至多有log次，次数不多。
所以我们可以对整个序列做至多log次FWT，求出至少在第几次存在异或值等于总异或值，n-次数即为答案。
以下代码：
#include<bits/stdc++.h> #define il inline #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=6e5+5; int n,a[N],t=1,l,mx,sum,v[N],b[N],c[N]; il int read(){int x;char ch;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x;} il void fwt(int *s,int tp){ for(int i=1;i<t;i<<=1){ for(int j=0;j<t;j+=i<<1){ for(int k=0;k<i;k++){ int A=s[j+k],B=s[i+j+k]; s[j+k]=A+B;s[i+j+k]=A-B; if(tp==-1)s[j+k]=s[j+k]/2,s[i+j+k]=s[i+j+k]/2; } } } } int main() { n=read();for(int i=1;i<=n;i++){int x=read();b[x]=1;mx=max(mx,x);sum^=x;} while(t<=mx)t<<=1,l++; if(sum==0){printf("%d ",n);return 0;} if(b[sum]){printf("%d ",n-1);return 0;} fwt(b,1);for(int i=0;i<t;i++)c[i]=b[i]; for(int k=1;;k++){ if(k>1){ for(int i=0;i<t;i++)if(c[i]!=0)c[i]=1; fwt(c,1); } for(int i=0;i<t;i++)c[i]=c[i]*b[i]; fwt(c,-1); if(c[sum]!=0){printf("%d ",n-k-1);return 0;} } return 0; }