AC手记

记录从暴力到最优的每一步

0%

【线性代数】

发表于 更新于 分类于 1.2k 1 分钟

【线性代数】

线性基

三维立体空间中任意一个向量都可以用三个基向量$i,j,k$表示。
三维立体空间是特殊的线性空间，其基向量在线性空间中被推广为线性基。

异或线性基

对于一个数列$A$，$P$是它的一组异或线性基。则

  • $P$中任意非空子集的异或和不为$0$
  • $P$中数的最高位（二进制）的$1$不重复
  • $P$中数的个数$\leq A$中数的个数
  • $A$中任意数字都能通过$P$中的一些数字异或得到

异或线性基的应用

  • 判断一个数是否能表示成某数集的子集的异或和
  • 求一个数表示成某数集的子集的异或和的方案数
  • 求某数集子集的最大、最小、第$k$大、第$k$小的异或和
  • 求一个数在某数集子集异或和中的排名

异或线性基的构造方法

贪心法和高斯消元法

P3812 【模板】线性基 - 洛谷

模板：

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// 二进制线性基（支持 long long）
struct LinearBasis
{
    static const int LOG = 63; // 最高位（long long 用 0~62）
    vector<ll> d;              // d[i] 表示最高位是 i 的基向量

    LinearBasis()
    {
        d.resize(LOG + 1, 0);
    }

    // 插入一个数到线性基
    bool insert(ll x)
    {
        for (int i = LOG; i >= 0; i--)
        {
            if (!(x >> i & 1))
                continue;

            if (!d[i])
            { // 如果该位还没有基向量
                d[i] = x;
                return true; // 插入成功（线性无关）
            }

            x ^= d[i]; // 消掉最高位
        }
        return false; // 插入失败（线性相关）
    }

    // 查询最大异或和
    ll queryMax()
    {
        ll res = 0;
        for (int i = LOG; i >= 0; i--)
        {
            res = max(res, res ^ d[i]);
        }
        return res;
    }

    // 查询最小非零异或和
    ll queryMin()
    {
        for (int i = 0; i <= LOG; i++)
        {
            if (d[i])
                return d[i];
        }
        return 0;
    }

    // 判断 x 是否能被表示出来
    bool canRepresent(long long x)
    {
        for (int i = LOG; i >= 0; i--)
        {
            if (!(x >> i & 1))
                continue;
            if (!d[i])
                return false;
            x ^= d[i];
        }
        return true;
    }
};