线性基学习笔记

首先看一道题：洛谷 P3812 【模板】线性基

题目名称已经说明了算法是什么，毕竟是一道模板题对吧。。。

线性基是什么？

哈？学过线性代数或者高斯消元的都应该知道吧。。。

不知道的左转出门自行百度。。。

或者参考这两篇博客：

P3812 【【模板】线性基】

线性基学习笔记

在竞赛中，提到线性基，一般是指异或线性基。

实际上上面两篇博客已经把该奖的都差不多讲完了。

其实线性基还可以合并。

两个线性基合并就是暴力把某个线性基强行插入另外一个线性基。

代码的话，可以写成结构体重载加法：

struct Linear_Basis{
    long long base[MAXN]={0};
    bool zero=false;
    bool insert(long long x){
        for(int i=63;~i;i--)if(x&(1LL<<i)){
            if(!base[i]){base[i]=x;return true;}
            else x^=base[i];
        }
        zero=true;
        return false;
    }
    friend Linear_Basis operator +(const Linear_Basis &u,const Linear_Basis &v){
        Linear_Basis ret;
        for(int i=63;~i;i--){
            if(u.base[i])ret.insert(u.base[i]);
            if(v.base[i])ret.insert(v.base[i]);
        }
        ret.zero=u.zero|v.zero;
        return ret;
    }
};

至此，基本上线性基的基本操作都搞完了。

是时候拿出犹大练手题了！

洛谷 P3812 【模板】线性基

板子题，放个代码在这吧。

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 70
using namespace std;
int n;
int top=0;
long long stack[MAXN];
struct Linear_Basis{
    long long base[MAXN]={0};
    bool zero=false;
    void init(){
        zero=false;
        for(int i=0;i<=64;i++)base[i]=0;
    }
    bool insert(long long x){
        for(int i=63;~i;i--)if(x&(1LL<<i)){
            if(!base[i]){base[i]=x;return true;}
            else x^=base[i];
        }
        zero=true;
        return false;
    }
    bool check(long long x){
        if(!x)return zero;
        for(int i=63;~i;i--)if(x&(1LL<<i)){
            if(!base[i])return false;
            x^=base[i];
        }
        return true;
    }
    long long query_max(long long s){
        for(int i=63;~i;i--)s=max(s,s^base[i]);
        return s;
    }
    long long query_min(){
        if(zero)return 0;
        for(int i=0;i<=63;i++)if(base[i])return base[i];
    }
    long long query(long long k){
        long long s=0;
        k-=zero;
        if(!k)return 0;
        for(int i=0;i<=63;i++){
            for(int j=i-1;~j;j--)if(base[i]&(1LL<<j))base[i]^=base[j];
            if(base[i])stack[++top]=base[i];
        }
        if(k>=(1LL<<(top-1)))return -1;
        while(top){
            if(k&(1LL<<(top-1)))s^=stack[top];
            stack[top--]=0;
        }
        return s;
    }
    friend Linear_Basis operator +(const Linear_Basis &u,const Linear_Basis &v){
        Linear_Basis ret;
        for(int i=63;~i;i--){
            if(u.base[i])ret.insert(u.base[i]);
            if(v.base[i])ret.insert(v.base[i]);
        }
        ret.zero=u.zero|v.zero;
        return ret;
    }
}a;
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline long long read(){
    long long date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
void init(){
    long long x;
    n=read();
    for(int i=1;i<=n;i++){
        x=read();
        a.insert(x);
    }
}
int main(){
    init();
    printf("%lld\n",a.query_max(0));
    return 0;
}

xor序列

这是一道基本题。

[CQOI2013]新NIM游戏

就是个游戏的变形。

无效位置

[JLOI2015]装备购买

这是一道在线性代数里的线性基，就是正常的加减法线性基。