线性基的技巧
写的比较简单,自用
正常的线性空间的运算符是\(+,\cdot\),而算法竞赛中我们可以\(\mathrm{XOR},\cdot\),并把二进制数看成一个k维向量来解决问题。
线性基,就是一组线性无关的向量
线性基的构建
void insert(ll v){
for(int i=maxlogv;i>=0;i--){
if(v&(1ll<<i)){
if(p[i]) v^=p[i];
else{
p[i]=v;
break;
}
}
}
这实际上是一个高斯消元的过程。
每次加入一个二进制数,相当于对新一行消元,对于这一行的第\(i\)个变量,我们和第\(i\)行异或,就可以把它消掉。这样构造出来的是一个上三角矩阵。不过矩阵经过了压缩,把某些不同行的1压到了一起。
void insert(ll v){
for(int i=maxlogv;i>=0;i--){
if(v&(1ll<<i)){
if(p[i]) v^=p[i];
else{
p[i]=v;
//若维护成对角矩阵,就这样加上2行
for(int k=i-1;k>=0;k--) if(p[k]&&(p[i]&(1ll<<k))) p[i]^=p[k];//先用下面的行消自己，再用自己消上面的行
for(int k=i+1;k<=maxlogv;k++) if(p[k]&(1ll<<i)) p[k]^=p[i];
break;
}
}
}
}
这是线性基的另一种写法。这种写法消出的是一个对角矩阵。这种写法在求第\(k\)大时有用
求最大/最小异或和
从高位往低位贪心。若是上三角矩阵,可能会把后面原有的1消掉,所以要取max.若是对角矩阵,第\(i\)位是第一次为1,直接取
ll query(){
ll ans=0;
//若维护成对角矩阵,直接xor即可,否则需要取max
for(int i=maxlogv;i>=0;i--) if((ans^p[i])>ans) ans^=p[i];
return ans;
}
如果要询问数\(x\)与集合中的数的异或最值,令ans=x即可
求第k小异或和
消成上三角矩阵后,假设基中有\(m\)个元素,那么能构造出的异或和有\(2^m\)种.把基中元素从小到大排序,再运用二进制分组的思想,如果k的第\(i\)位为1，就加上\(p_i\),这样就可以得到第\(k\)大。注意如果插入了元素0,0不会出现在线性基中,需要特判.
//http://acm.hdu.edu.cn/showproblem.php?pid=3949
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxlogv 50
using namespace std;
typedef long long ll;
int n,q;
void bprint(int x){
for(int i=5;i>=0;i--){
if(x&(1ll<<i)) putchar('1');
else putchar('0');
}
}
struct linear{
ll p[maxlogv+5];
bool hasZero;
vector<int>vec;
void clear(){
vec.clear();
hasZero=0;
memset(p,0,sizeof(p));
}
void insert(ll v){
for(int i=maxlogv;i>=0;i--){
if(v&(1ll<<i)){
if(p[i]) v^=p[i];
else{
p[i]=v;
//若维护成对角矩阵,就这样加上2行
for(int k=i-1;k>=0;k--) if(p[k]&&(p[i]&(1ll<<k))) p[i]^=p[k];//先用下面的行消自己，再用自己消上面的行
for(int k=i+1;k<=maxlogv;k++) if(p[k]&(1ll<<i)) p[k]^=p[i];
break;
}
}
}
if(v==0) hasZero=1;
}
void build(){
for(int i=0;i<=maxlogv;i++) if(p[i]) vec.push_back(p[i]);
}
ll kth(ll k){//第k小xor和
ll ans=0;
if(hasZero) k--;
if(k>=(1ll<<(int)vec.size())) return -1;
for(int i=0;i<(int)vec.size();i++) if(k&(1ll<<i)) ans^=vec[i];
return ans;
}
}T;
int main(){
ll x;int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
T.clear();
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&x);
T.insert(x);
}
printf("Case #%d:\n",cas);
scanf("%d",&q);
T.build();
for(int i=1;i<=q;i++){
scanf("%lld",&x);
printf("%lld\n",T.kth(x));
}
}
}
线性基上的贪心
给每个元素一个权值\(w_x\),求一个权值和最大/最小的基。可以贪心,按\(w\)排序后依次插入即可。根据拟阵可以证明最优性