异或空间与异或基

字数统计: 1.5k字 | 阅读时长: 6分

2020-11-24

代数28

摘要: 本文介绍异或基的算法原理和代码模板。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章高斯消元与线性方程组中，我们学习了高斯消元的原理和代码模板。之后在高斯消元算法的基础上，我们在文章线性空间与线性基中进一步学习了线性基的概念以及如何用高斯消元求线性基。

本文我们看一下异或空间的概念，异或空间也是一种线性空间，类似地也有极大线性无关线组，称为异或基，那么自然也可以通过高斯消元可以求出异或空间的秩和异或基。最后通过一道经典的题，给出使用高斯消元求异或基的代码模板。

$1 异或空间

线性空间的概念可以推广，例如异或空间。

异或空间是一个关于异或运算封闭的非负整数集合。

在异或空间中可以类似地定义表出，线性无关，基。

表出

若整数 b 能由整数 $a_{1}, a_{2}, …, a_{k}$ 经过异或运算得出，称 b 能被$a_{1}, a_{2}, …, a_{k}$ 表出。

$a_{1}, a_{2}, …, a_{k}$ 能够表出的所有整数构成一个异或空间，$a_{1}, a_{2}, …, a_{k}$ 称为这个异或空间的生成子集。

线性无关

任选异或空间中的若干整数，如果其中存在一个整数可以由其它的整数表出，称这些整数线性相关。否则线性无关。

异或空间的基

定义1：异或空间中的线性无关的生成子集。
定义1：异或空间中的极大线性无关子集。

$2 异或空间的基的求法

求 n 个 $[0,2^{m}-1]$ 之间的整数 $a_{1},…,a_{n}$ 的基

把他们看做 m 位二进制数，写成一个 n 行 m 列的 01 矩阵。

矩阵中第 i 行从左到右依次是 $a_{i}$ 的第 m-1, m-2, …, 1, 0 位。

此矩阵作为系数矩阵，用高斯消元求解异或方程组，将其霍建伟简化阶梯形矩阵。

简化后的矩阵所有非零整数一起构成异或空间的基。

$3 题目

210. 异或运算

给定你由N个整数构成的整数序列，你可以从中选取一些（甚至一个）进行异或（XOR）运算，从而得到很多不同的结果。

请问，所有能得到的不同的结果中第k小的结果是多少。

所有数字在 1 ~ 1e18 之间

分析

(1) 求异或空间的基

N 个整数 a[1] ~ A[N]。用高斯消元求这 A 个整数构成的异或空间的基。

设基为 b[1] ~ b[t]，其中 b[1] > b[2] > ... > b[t]，空间中总共有 2^t 个整数。

高斯消元过程中，共有 t 个主元，分别为 b[1], b[2], ..., b[t] 的最高位，记 b[1], b[2], ..., b[t] 的最高位为 c[1], c[2], ..., c[t]，同样有 c[1] > c[2] > ..., > c[t]

在简化阶梯型矩阵中，对于每个主元，有且仅有一个 (i, j) 满足该主元的系数非零，第 j 列其它位置都是零。

(2) 求空间中的第 k 小元素

基为 b[1] ~ b[t]，其中 b[1] > b[2] > ... > b[t]，求能表出的第 k 小整数。

因为第 c[1] 为为 1 的仅有 b[1]，因此选 b[1] 一定比不选 b[1] 所得的数大。

同理，选了 b[1] 之后，选 b[2] 一定比不选 b[2] 所得的数大。

异或空间最大的数是将 b[1] ~ b[t] 全都异或起来的最大的数。

把 k - 1 二进制分解(k - 1 是因为把最小的定义为第 0 小)，如果 k - 1 的第 0 <= j < t 位等于 1, 就选取 b[t - j]，把所有选出的 b 异或起来得到答案。如果 k > 2^t 则无解。

由于本题中不允许 a[i] ^ a[i]，而异或空间允许，因此异或空间一定含 0，但 a[1] ~ a[n] 选出几个不同的数异或可能得不到 0。此时就对 k 二进制分解而不是 k - 1。

可以检查简化阶梯型矩阵中知否存在零行，如果有，则可以得到零。

代码 (C++)

#include <vector>
#include <iostream>

using namespace std;

using ULL = unsigned long long;

int main()
{
    int T;
    cin >> T;
    for(int C = 1; C <= T; ++C)
    {
        int N;
        cin >> N;
        vector<ULL> a(N + 1);
        for(int i = 1; i <= N; ++i)
            cin >> a[i];

        vector<ULL> b; // 异或空间的基

        int dim = 0;
        bool zero = false; // 标记简化阶梯型矩阵是否有全零行
        for(int i = 1; i <= N; ++i) // 处理第 i 行
        {
            // 选行，选 dim + 1 位为 1 的
            // 状态压缩的情况下，可以直接选数值最大的
            for(int j = i + 1; j <= N; ++j)
            {
                if(a[j] > a[i])
                    swap(a[i], a[j]);
            }
            if(a[i] == 0) // 此后都是全零行了
            {
                zero = true;
                break;
            }
            ++dim;
            // 消
            for(int k = 63; k >= 0; --k)
                if(a[i] >> k & 1)
                {
                    for(int j = 1; j <= N; ++j)
                    {
                        if(i == j) continue;
                        if(a[j] >> k & 1)
                            a[j] ^= a[i];
                    }
                    break;
                }
        }
        // 阶梯型矩阵 a 的前 dim 行是基 a[1 ~ dim]

        // 处理询问
        int Q;
        cin >> Q;
        cout << "Case #" << C << ":" << endl;
        while(Q--)
        {
            ULL k;
            cin >> k;
            if(zero) --k;
            ULL ans = 0;
            if(k >= (ULL)1 << dim)
                cout << "-1" << endl;
            else
            {
                for(int i = dim - 1; i >= 0; --i)
                {
                    if(k >> i & 1)
                        ans ^= a[dim - i];
                }
                cout << ans << endl;
            }
        }
    }
}

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

数代数