线性基总结

线性基总结

线性基是处理异或问题的有力工具
如果把正整数按照二进制来看,每一位相当于一维,
这样每个数就都成了一个32维的向量,那么线性基就可以完全且恰好的表示成这些向量所围成的图形

性质

线性基有很多优秀的性质
1.线性基就是与原集合的值域完全相同的最小集合
，所以线性基中的所有元素可以且只能唯一的表示出原集合中元素的任意异或组合
2.线性基的每一维的数在二进制下的最高位一定是这一维的位数
3.所有线性基进行异或的组合,每种权值只会出现一次且不会得到0
4.如果一个元素无法加入线性基就说明这个元素可以被线性基内的元素通过异或表示出
5.如果有\(k\)个元素不能加入线性基,那么线性基通过组合得到的每个元素在原集合的组合下都会恰好出现\(2^k\)次

应用

1.线性基的插入

从高位向低位插入
具体原理类似于高斯消元解异或方程组

inline bool Ins(int x) {
    for(int i = 62 ; i >= 0 ; i --)
        if(x & (1ull << i)) {
            if(!lib[i]) { lib[i] = x ; return true ; }
            else x ^= lib[i] ;
        }
    return false ;
}

2.线性基求最大的异或和

因为线性基可以完全的表示原有集合的值域,所以可以直接从高位向低位贪心,当贪心到第\(k\)位,后面的位数通过后面的线性基一定可以组合出来

inline int Gmax() {
    int ans = 0 ;
    for(int i = 30 ; i >= 0 ; i --) 
        ans = max(ans , ans ^ lib[i]) ;
    return ans ;
}

3.查询线性基所组合出的数的第k小

首先,我们要先对原来的每一维的线性基进行预处理,让第i维的线性基表示的是最高位为第i位的组合出的最小的数,然后如果这一位始终无法组合出1来,那么就舍弃这一位

inline void presolve() {
    for(int i = 30 ; i >= 0 ; i --) 
        for(int j = i - 1 ; j >= 0 ; j --)
                lib[i] = min(lib[i] , lib[i] ^ lib[j]) ;
    for(int i = 0 ; i <= 62 ; i ++)
        if(lib[i]) p[cnt ++] = lib[i] ;
}

这样以后就可以看出,一共有\(2^{cnt}-1\)种组合方案,能组合出\(2^{cnt}-1\)种数,那么我们就按照\(k\)来贪心的取就好了，如果\(k\)的第\(t\)位为1就异或上当前这一位的线性基,由于处理过线性基表示最高位为这一位的最小值,所以排名恰好去掉\(2^t\),类似于倍增LCA

inline int kth(int k) {
    int ret = 0 ;
    if(k >= (1ull << cnt)) return (1ull << cnt) ;
    for(int i = 30 ; i >= 0 ; i --)
        if(k & (1ull << i))
            ret ^= p[i] ;
    return ret ;
}

4.查询线性基组合出的数的排名

首先还是和刚才那样先对线性基预处理一下,然后如果查询到第k位，要查询的数的这一位是1,那么就将答案加上\(2^k\),具体原因是因为我们处理后的线性基表示的是满足最高位是这一位的最小值,所以排名恰好增加\(2^k\)，类似于倍增LCA

inline int Grnk(int k) {
    int ans = 0 ;
    for(int i = 0 ; i < cnt ; i ++)
        if(k & (1ull << i))
            ans = (ans + (1ull << i)) ; 
    return ans ;
} 

5.求最大异或环

可以轻易发现,两个环经过异或后可以形成一个大的环,所以我们就只需要找出所有的简单环并把所有简单环加入线性基求最大异或和就好了,那么我们就先把原图搞成一棵树,然后加入那些非树边,这样就保证了能加入所有的简单环,加入的答案就是\(dis(u)^dis(v)^w(u,v)\)

线性基总结

原文：https://www.cnblogs.com/beretty/p/10389472.html