Luobuyu's Blog

0%

线性基

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 2.5k 阅读时长 ≈ 2 分钟
线性基定义已经一般用法。

线性基

一、定义

考虑将 $ n $ 个数（二进制下）看成 $ n $ 个向量，每个向量中的每个元素仅有 $ 0、1 $ 两种取值。如果向量 $ X $ 能被 $ a_1,a_2,\cdots,a_n $ 这些向量通过异或运算得到，则称 $ X $ 能被 $ a_1,a_2,\cdots,a_n $ 表出。如果某个向量集合中存在若干个向量能被其它向量表出，则这些向量线性相关，否则线性无关，

定义一个向量集合的线性基为其极大线性无关子集（可能有多个线性基，但这没有关系）（显然线性基可以表出这个向量集合）
线性空间是对异或运算封闭的向量集合。

另外，异或高斯消元仅有向量间的异或操作，所以消元不会改变这些向量能表出的线性空间。因此，高斯消元可以求得一组线性基。

线性基可以看做一个数的集合，并且每个序列都拥有至少一个线性基。

若干数的线性基是一组数 $ a_1,a_2,…a_n $ ，其中 $ a_x $ 的最高位的 1 在第 $ x $ 位。
通过线性基中元素 xor 出的数的值域与原来的数 xor 出数的值域相同。
设线性基中的元素为 $ p_1,p_2,\dots,p_n $ ( $ p_i $ 的数在二进制表示下第 $ i $ 位是该数字的最高位 1)则 $ a_1,a_2,\cdots ,a_n $ 可用 $ p_1,p_2,\cdots, p_n $ 通过 xor 运算得出

其实就像是高斯消元，不过高斯消元复杂度有点高。

二、性质

通俗一点的讲法就是由一个集合构造出来的另一个集合，它有以下几个性质：

  • 线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。
  • 线性基是满足性质 1 的最小的集合。
  • 线性基没有异或和为 0 的子集。
  • 线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。
  • 线性基中每个元素的二进制最高位互不相同。

三、用法

一般有三种用法：

  1. 查询一个数能否被集合中其他数异或表示。
  2. 求一个集合异或能够得到的最大值或最小值。
  3. 求一个集合异或能够得到的第 k 大值。

实现这些之前都需要先构造得到集合的一组线性基。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insert(ll x) {
    for(int i = 63; i >= 0; i--)
    {
        if(x & (1LL << i))
        {
            if(!p[i])
            {
                p[i] = x;
                break;
            }
            x ^= p[i];
        }
    }
}

即根据定义，从大到小枚举当前 $ x_{(2)} $ 的第 i 位，如果发现 $ p_i $ 已经有元素了，就让 x = x ^ p[i]，否则就插入当前的 $ x $ .

如果一个数 $ z $ 插入不进去，那么必有 $ p_i $ 每一位都已经有元素了，异或到最后 $ z \oplus p_x \oplus p_{x-1} \oplus \cdots \oplus p_0 = 0 $ 根据异或性质可以得到 $ p_x \oplus p_{x-1} \oplus \cdots \oplus p_0 = z $ ，说明此时 $ z $ 已经能够被线性基中的其他元素表示了，自然插入不进去。

  1. 查询是否能异或出来

    从高到低，如果该位不为零，就把该位消掉，如果最后得到了 $ 0 $ ，那么就可以表示出来（实际上就是插入的操作，因为异或 $ 0 $ 不变，所以就是插入操作）

    1
    2
    3
    4
    5
    6
    7
    8
    bool query(ll x)
    {
        for(int i = 63; i >= 0i--)
        {
            if(x&(1ll<<i)) x ^= p[i];
        }
        return x == 0;
    }

  2. 查询异或最大值

    从高到低，贪心异或即可

    将线性基从高位向低位扫，若 xor 上当前扫到的 $ p_i $ 答案变大，就把答案异或上 $ p_i $ 。

    为什么能行呢？因为从高往低位扫，若当前扫到第 $ i $ 位，意味着可以保证答案的第 $ i $ 位为 1，且后面没有机会改变第 $ i $ 位。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    ll getMax()
    {
        ll ans = 0;
        for(ll i = 63; i >= 0; i--)
        {
            ans = max(ans, ans ^ p[i]);
        }
        return ans;
    }

  3. 查询一个集合异或最小值。

    注意这里指用线性基能够异或出的最小值。最小值为最小的 $ p_i $

    如果求的是整个序列能异或出的最小值，那么要看有没有元素不能插入线性基，就是能不能表出。如果能，最小值就是 $ 0 $ .

  4. 查询一个集合异或的第 $ k $ 大值

    首先需要对线性基处理一下，对于每一个 $ p_i $ ，枚举 $ j(i\to 0) $ ，如果 $ p_i $ 的第 $ j $ 位为 $ 1 $ ，那么 $ p_i \oplus p_j $ 。实际上就是只把最前面的 $ 1 $ 保留着，后面的都消掉。

    注意第 $ k $ 大和第 $ k $ 小的区别。第 $ k $ 小需要考虑到 $ 0 $ 。第 $ k $ 大需要考虑到 $ k $ 太大了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    int cnt = 0;
    ll d[maxn];
    void rebuild()
    {
        for(int i = 63; i >= 0; i--)
        {
            for(int j = i - 1; j >= 0; j--)
            {
                if(p[i] & (1ll << j)) p[i] ^= p[j];
            }
        }
        for(int i = 0; i <= 63; i++) 
        {
            if(p[i])
            {
                d[cnt++] = p[i];
            }
        }
    }
    ll queryKMax(ll k)
    {
        if(k >= (1ll << cnt)) return -1;
        ll ans = 0;
        for(int i = 63; i >= 0; i--)
        {
            if((1ll << i) & k)
            {
                ans ^= d[i];
            }
        }
        return ans;
    }
    ll queryKMin(ll k)
    {
        if(k == 1 && cnt < n) return 0;
        if(cnt < n) k--; // 因为不能搞出0
        ll ans = 0;
        for(int i = 0; i <= 63; i++)
        {
            if(k & (1ll << i))
            {
                ans = d[i];
            }
        }
        return ans;
    }