线性基学习笔记

线性基学习笔记

线性基是什么》》》

给定一个序列 (A=a_1, a_2, a_3 cdots a_n) ，定义集合 (S) 为 (A) 子集的异或和组成的集合。

一个集合 (B) 使得 (S) 中的数可以由 (B) 中的几个数异或得到，且 (B) 的任意真子集不满足该性质，则 (B) 为 (A) 的线性基。

怎么求线性基？

把 (A) 中的数一个一个插入线性基即可。

插入方法：设现在已经得到的线性基为 (A_0) ，插入的数为 (x) ，从高到低扫描 (x) 的二进制位，如果这一位上有基，就把 (x) (xor) (a_i) 知道找到第一个没有基的位置，否则 (x) 不对线性基造成影响。

证明：别问 问就是不会；（按照上述证明过程，显然 (A) 中每个数的 (1) 都可以由线性基里的数得到，且不难发现 (forall_j b_j) 第 (j) 位之前都是 (0)

代码实现：

struct linear_basis {
    ll a[65];
    inline void insert(ll x) {
        if(!x) return ;
        for(int i=maxl;i>=0;i--)
            if(x&(1ll<<i)) {
                if(!a[i]) { a[i]=x; break; }
                x^=a[i];
            }
    }

}B;

一些应用

在 (n) 个数中选若干个数的最大异或和

在得到线性基后，只需从高到低考虑 线性基中的数是否会使答案增大即可。

在一个无向连通图中找一条从1到n的路径，使路径长度异或和最大

显然，这条路径由一条链和若干环组成，所以可以先 (dfs) 找到一条链；

不难发现，这条链发生变化当且仅当链上的两个节点之间的路径发生改变，改变前后的两段刚好是一个环；

所以，任意一条链可以通过异或这个环的异或和得到；

考虑环，有一部分在链上的环已经考虑过，只需考虑不在链上的；

显然从环到链这一段是无效的；

所以把环的异或和插入线性基即可；