题解 P3812 【【模板】线性基】

本人二进制渣渣。。 然后。。看不懂概念。。。不知道为什么可以这么做。。 https://www.cnblogs.com/ljh2000-jump/p/5869991.html 上面的博客详细写了如何构造线性基，查询最大值，判断一个值是否可以被xor出来。但是。。。。。没写为什么。。。 然后。。。关于详细的证明和概念 https://blog.sengxian.com/algorithms/linear-basis 虽然我一个字都看不懂。。。。 然后，根据第一个博客我硬是敲了出来。。（因为很好敲） ```cpp #include<cstdio> #include<cstring> #include<iostream> using namespace std; int n; long long a[100],f[60],b[60]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); f[0]=1; for(int i=1;i<=55;i++) f[i]=f[i-1]*2; for(int i=1;i<=n;i++) for(int j=55;j>=0;j--) if(a[i]&f[j]) { if(!b[j]) { b[j]=a[i]; break; } else a[i]^=b[j]; } long long ans=0; for(int i=55;i>=0;i--) if((ans^b[i])>ans) ans^=b[i];//这里写(ans^f[i])>ans貌似也可以。不知道为啥 printf("%lld",ans); return 0; } ```