【学习笔记】线性基

· · 个人记录

模拟赛遇到一个笨比线性基题但是忘了怎么求编号......最后因读入T掉来不及修改赛后20s过题，惨痛教训。

线性基是一组极小的用于表达一个数集异或空间的基底。其满足以下性质：

1.能由原数集异或得到的任意一个数，线性基中都有且仅有一个子集能表示它。

2.由1得，线性基中不存在一个数能被其它元素异或得到。

3.由2得，线性基中不存在异或和为 0 的子集。

线性基不是唯一的，且不一定需要满足最高位互不相同，但我们构造时需要构造一个最高位互不相同的线性基，这样才能在加入元素时通过贪心判断新元素能否被原线性基表达。

假设我们已经有了一个最高位互不相同的线性基，现在加入一个新元素：

显然不论我们以任何顺序插入元素，线性基大小都相同，得到以下性质：所有线性基大小相同，即对一个数集求线性无关的基底则其大小固定。

由此，我们构造线性基的代码已经可以写出来了：

for(int k=50; k>=0; k--) {          
    if(num&(1ll<<k)) {              
    if(!p[k]) {p[k]=num;break;}             
    num^=p[k];          
}
拓展：如何求原数集子集异或和的集合大小? 显然线性基的任意一个子集的异或和都不相同，所以其为 $2^{线性基大小}

拓展：线性基构造出来的数，如何输出原数集中的对应方案？

我们对线性基中的每一个数用一个 bitset 记录其是由原数集中的哪些数异或得到的。具体而言：

bitset<N> pid[55];
for(int i=1; i<=n; i++) {
    cin>>a[i];
    bitset<N> id; id[i]=1;  
    for(int k=50; k>=0; k--) {          
        if(a[i]&(1ll<<k)) {             
        if(!p[k]) {p[k]=a[i],pid[k]=id;break;}              
        a[i]^=p[k],id^=pid[k];          
    }
}

用线性基构造时，使用的基向量的 pid 异或和即为对应的原数集集合。

线性基的用处：

1.判断某个数是否可以被原数集的某个子集异或得到。

与往线性基中加数相同。

进阶： 判断某个数被原数集的某个子集异或得到的方案数。

任何数被线性基异或得到的方案数唯一，考虑没能加入线性基的数有 k 个，显然这 k 个数任选一个子集都能用线性基中的一个子集使其贡献为 0 ，因而每个数会有 2^k 中表达方法

2.判断原数集异或能得到的最大/最小值。

从高位到低位贪心，若该位为 0 且存在最高位为此位的基向量，则异或此基向量即可。

for(int i=50; i>=0; i--) if(!(ans&(1ll<<i))) ans^=p[i];

进阶：判断原数集异或能得到的第 k 小值。

显然对于某个存在最高位为该位的位，我们都可以自由控制该位是否为 1 。

因此如果我们设置该位为 1 ，则增加了 2^{最高位低于该位的基向量个数} 个小于它的数。

ll ans=0,p=cnt;
for(Reg int i=62;i>=0;--i){
    if(!b[i]) continue;
    if(ans&(1ll<<i)){
        if(k>(1ll<<(p-1))) k-=(1ll<<(p-1)),ans^=b[i];
    }else{
        if(k>(1ll<<(p-1))) k-=(1ll<<(p-1));
        else ans^=b[i];
    }
    --p;
}

拓展：对于不去重的排名，考虑没能加入线性基的数有 k 个，显然这 k 个数任选一个子集都能用线性基中的一个子集使其贡献为 0 ，因而每个数会重复 2^k 次，若原答案为 ans ，则不去重的答案为 2^{ans-1}+1 。

3.求一个数在原数集异或和中的排名。

与上类似，先判断该数能否被线性基表达出来，再依次枚举每位线性基中存在的位，加上 2^{最高位低于该位的基向量个数} 即可。

带删除线性基

首先需要知道每个时间点都干了些什么，如果是加了个数就需要预处理出这个数会在哪里被删掉。处理好这个之后，我们仍然按照时间处理操作，但是需要给插入线性基的数一个时间戳表示这个数被删除的时间，查询的时候只查询时间戳在当前时间之后的。对于线性基的每一位，时间戳应优先保留靠后的一个。

constexpr int MAXN=5e5+5;
int n,a[MAXN],del[MAXN];
unordered_map<int,int>mp;
struct{
    int p[32],t[32];
    void ins(int x,int tim){
        for(int i=30;~i;i--){
            if(!(x>>i)) continue;
            if(tim>t[i]) swap(x,p[i]),swap(tim,t[i]);
            if(!tim) return;
            x^=p[i];
        }
    }
    int ask(int tim){
        int res=0;
        for(int i=30;~i;i--) if(tim<t[i]) res=max(res,res^p[i]);
        return res;
    }
}LB;

int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(a[i]>0) mp[a[i]]=i,del[i]=n+1;
        else del[mp[-a[i]]]=i;
    }
    for(int i=1;i<=n;i++){
        if(a[i]>0) LB.ins(a[i],del[i]);
        write(LB.ask(i));
    }
    return fw,0;
}