线性基算法整理(模板)

简介

你有一个原集合T;

线性基是一个集合，里边的元素通过异或，可以不多不少的凑出T，且线型基最小；

性质

1.设线性基的异或集合中不存在0。

2.线性基的异或集合中每个元素的异或方案唯一，其实这个跟性质1是等价的。

3.线性基二进制最高位互不相同。

4.如果线性基是满的，它的异或集合为[1,2n−1]。

5.线性基中元素互相异或，异或集合不变。

用途

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

实现

线性基数组bit[i]代表第一次出现的二进制最高位是i的数字,对于每个数组从最高位开始枚举,若这一位的bit已存在,那么就将这个数异或bit[i],否则就将bit[i]记录为x,终止循环。

如此找最大的异或和便成了一个贪心的问题了,从最高位开始枚举,若这一位存在,则异或这一位一定不会让答案变得更差。

#include<bits/stdc++.h> using namespace std; #define Sheryang main const int maxn=2e6+7; typedef long long ll; const int mod=1e9+7; //#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) //char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf; #define IO cin.tie(0),ios::sync_with_stdio(false); #define pi acos(-1) #define PII pair<ll,ll> ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;} #define read read() /** keep hungry and keep calm! **/ ll a[100],bit[100]; void solve(ll x){ for(int i=60;i>=0;i--){ if((x>>i)&1){ if(bit[i]==0){ bit[i] = x; return; } x ^= bit[i]; } } } int Sheryang(){ int n = read; for(int i=0;i<n;i++){ solve(a[i]=read); } ll ans = 0; for(int i=60;i>=0;i--){ if((ans^bit[i]) > ans){ ans ^= bit[i]; } } printf("%lld\n",ans); return 0; }