线性基

江湖规矩，先%mmh 例①：P3812 【模板】线性基： 题目背景 这是一道模板题。

题目描述 给定n个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。

输入格式 第一行一个数n，表示元素个数

接下来一行n个数

输出格式 仅一行，表示答案。

输入输出样例 输入 #1 复制 2 1 1 输出 #1 复制 1 说明/提示 1≤n≤50,0≤Si≤2⁵⁰

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<vector> #include<cmath> #define ll long long #define llu unsigned ll using namespace std; const int inf=0x3f3f3f3f; const ll lnf=0x3f3f3f3f3f3f3f3f; ll p[100]; void _insert(ll val) { for(int i=63;i>=0;i--) { if(val&(1ll<<i)) { if(!p[i]) { p[i]=val; break; } else val^=p[i]; } } } ll get_max(void) { ll ans=0; for(int i=63;i>=0;i--) { if((ans^p[i])>ans) ans^=p[i]; } return ans; } int main(void) { ll n,x; scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&x); _insert(x); } printf("%lld\n",get_max()); return 0; }

例② 异或第k小。 Libre OJ #114. k 大异或和：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<vector> #include<cmath> #define ll long long #define llu unsigned ll using namespace std; const int inf=0x3f3f3f3f; const ll lnf=0x3f3f3f3f3f3f3f3f; ll p[100],cnt; ll np[100]; void _insert(ll val) { for(int i=63;i>=0;i--) { if(val&(1ll<<i)) { if(!p[i]) { p[i]=val; break; } else val^=p[i]; } } } //以下代码为求第k大异或值，其中cnt用于判断是否可以取到0 //cnt==n（数的个数）则不可以取到0，第k小就是第k小，否则第k小是第k-1小 void rebuild(void) { for(int i=63;i>=0;i--) { for(int j=i-1;j>=0;j--) { if(p[i]&(1ll<<j)) p[i]^=p[j]; } } for(int i=0;i<=63;i++) { if(p[i]) np[cnt++]=p[i]; } } ll get_kmin(ll k) { ll ans=0; if(k>=(1ll<<cnt)) return -1; for(int i=63;i>=0;i--) if(k&(1ll<<i)) ans^=np[i]; return ans; } int main(void) { ll n,m,x,k; scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&x); _insert(x); } rebuild(); int ff=0; if(cnt!=n) ff=1; scanf("%lld",&m); for(int i=1;i<=m;i++) { scanf("%lld",&k); printf("%lld\n",get_kmin(k-ff)); } return 0; }

还有另一种消元的线性基，思想一致，时间复杂度也是一样的。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<vector> #include<cmath> #define ll long long #define llu unsigned ll using namespace std; const int inf=0x3f3f3f3f; const ll lnf=0x3f3f3f3f3f3f3f3f; const int maxn=100010; ll a[maxn],cnt; void fi(ll n) { for(ll j=63;j>=0;j--) { ll k=0; for(k=cnt+1;k<=n;k++) if(a[k]&(1ll<<j)) break; if(k>n) continue; swap(a[k],a[++cnt]); for(int i=1;i<=n;i++) { if(i!=cnt&&a[i]&(1ll<<j)) a[i]^=a[cnt]; } } } ll get_kmin(ll k) { ll ans=0; if(k>=(1ll<<cnt)) return -1; for(int i=1;i<=cnt;i++) if(k&(1ll<<(cnt-i))) ans^=a[i]; return ans; } int main(void) { ll n,m,x,k; scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); fi(n); int ff=0; if(cnt!=n) ff=1; scanf("%lld",&m); for(int i=1;i<=m;i++) { scanf("%lld",&k); printf("%lld\n",get_kmin(k-ff)); } return 0; }