今天做题的时候听说了一个新的知识点,叫做线性基.于是来学一下,写个博客.

重要参考: Menci dalao的Blog

线性基的定义

张成

设$T\subseteq S$,所有这样的子集T的异或和组成的集合称为集合S的张成,记作 $span(S)$。即,在$S$中选出任意多个数,其异或和的所有可能的结果组成的集合。

线性相关

若集合$S$中存在一个元素$S_i$,使得$S$在去除这个元素后得到的集合$S’$的张成$span(S’)$中包含$S_i$,则称集合$S$线性相关

相对的,如果不存在这样的元素$S_i$,则称集合$S$线性无关

线性基

我们称集合$B$是集合$S$的线性基,当且仅当:

  1. $S\subseteq span(B)$,即$S$是$B$的张成的子集;

  2. $B$是线性无关的。

集合$B$中元素的个数,称为线性基的长度

(以上内容来自$Menci\ dalao$的博客,更多详细定义及内容请参考Menci dalao的Blog)

线性基的性质

我们由原集合构造出了原集合的线性基,这个集合中的数字满足以下性质:

  1. 从线性基中选择一些数异或起来,能够得到原集合中的任何一个数.换句话说,原集合中的任何一个数都可以用线性基中若干个数异或起来得到.
  2. 线性基是能够满足上一条性质的最小集合
  3. 线性基中的数无法得到0
  4. 线性基中所有满足$j<i$的$s[j]$的第$i$位以及更高位不可能是1,这一点由构造方法保证
  5. 整个线性基数组中只有$s[i]$的第$i$位是1.

形式化地,线性基s中的数满足$s_x\ xor\ s_y\ xor…xor\ s_z=a(x,y,z\in [1,sizeof(s)],a,s_x,s_y,s_z\in S)$.

线性基的主要作用

线性基可以用来解决一类特殊问题:在一列数中任选若干个,使得他们异或的结果最大.即求

$max{ a_i\ xor\ a_j\ xor …\ xor\ a_k},\ a_i,a_j…a_k\in S,i\neq j\neq…\neq k$.

这个问题我们采用线性基来解决.首先我们要明确线性基的构造方法.

for i 由高到低枚举数字t的每一个二进制位
    - 如果这一位是0,跳过,否则:
    - 如果s[i] == 0, t = t ^ s[i];
    - 如果s[i] == 1 then
        for j 循环[0,i) 如果t的第j位是1,则t=t^s[k];
        for j 循环(i,maxl] 如果s[j]的第i位是1,则s[j]=s[j]^t;
        s[i] = t;
算法结束.

最大子集异或和问题

这是线性基能解决的最基本问题.我们考虑让和最大,也就是让高位尽量为1.而且我们根据性质可以发现我们构造的线性基满足性质4和5,所以只有异或$s[i]$,才可能使得第i位变成1,所以我们可以直接把所有线性基中的数异或起来得到结果.

inline void insrt(int t) {//插入线性基
    for (int i = 63; i >= 0; --i) {//由高到低扫描
        if (t & (1ll << i) == 0) continue;
        if (s[i]) t ^= s[i];
        else {
            for (int j = 0; j < i; ++j)
                if (t & (1ll << j)) t ^= s[j];
            for (int j = i + 1; j <= 63; ++j)
                if (s[j] & (1ll << i)) s[j] ^= t;
            s[i] = t;
            return;
        }
    }
    return;
}

inline long long query(int t) {//最大异或和
    long long res = 0;
    for (int i = 0; i <= MAXL; i++) 
        res ^= a[i];
    return res;
}

这样问题就解决了.

——Gensokyo