DDOSvoid's Blog

线性基

发表于 更新于 分类于
本文字数： 3.1k 阅读时长 ≈ 3 分钟

简介

以后线性基统称为异或状态下的线性基

性质

  • 线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值

  • 线性基是满足性质 $1$ 的最小的集合

  • 线性基没有异或和为 $0$ 的子集

  • 线性基中每个元素的异或方案唯一，即线性基中不同的异或组合异或出的数是不一样的

  • 线性基中每个元素的二进制最高位互不相同

  • 令 $mx(v)$ 表示 $v$ 与线性基异或的最大值，$mn(v)$ 表示 $v$ 与线性基异或的最小值

    那么我们有

构造

首先我们参考线性代数中的线性基的构造方法，可以得到

1
2
3
4
5
6
7
void insert(int v) {
    for (int i = N; ~i; --i) {
        if (!(v >> i & 1)) continue;
        if (!a[i]) { a[i] = v; break; }
        v ^= a[i]; 
    } 
}

注意到我们依然是将这个向量看成行向量，这样插入之后我们就得到了一个行阶梯矩阵

应用

子集异或最大值/子集与 v 异或最大值

我们从高位到低位考虑，如果此时答案已经有第 $i$ 位，那么我们就不异或 $a[i]$，否则一定异或 $a[i]$

1
2
3
4
ll get_max(ll v = 0) {
    for (int i = N; ~i; --i) v = max(v, v ^ a[i]);
    return v; 
}

子集异或最最小值/子集与 v 异或最小值

我们从高位到低位考虑，如果此时答案已经有第 $i$ 位，那么我们一定异或 $a[i]$，否则不异或 $a[i]$

1
2
3
4
5
6
7
8
9
10
ll get_min() {
    if (O) return 0;
    for (int i = 0; i <= n; ++i)
        if (a[i]) return a[i];
}

ll get_min(ll v) {
    for (int i = n; ~i; --i) v = min(v, v ^ a[i]); 
    return v;
}

严格第 k 小子集异或值

注意到我们现在还是行阶梯，我们要进一步操作将其化成行最简形矩阵

化成行最简形之后第 $k$ 小就很明显了，因为每一个 $a[i]$ 都对应了二进制的第 $i$ 位

注意要特判 $0$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void work() {
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j < i; ++j)
            if (a[i] >> j & 1) a[i] ^= a[j];
} //先化为行最简形

ll get_kth(ll k) {
    ll ans = 0; k -= O; 
    for (int i = 0; i <= n; ++i) {
        if (!a[i]) continue;
        if (k & 1) ans ^= a[i];
        k >>= 1; 
    }
    if (k > 0) return -1; 
    else return ans; 
}

判断 x 是否存在于线性基中

我们直接使用插入的方法，判断最后 $x$ 是否为 $0$ 即可

1
2
3
4
5
6
7
8
bool check(ll v) {
    for (int i = n; ~i; --i) {
        if (!(v >> i & 1)) continue;
        if (!a[i]) return 0;
        v ^= a[i]; 
    } return 1;
}

给定 n 个数的集合求有多少子集异或和为 0

将所有数插入线性基，不妨设线性基内有 $k$ 个数，那么答案就是 $2^{n-k}-1$，原因也很简单线性基内的任何一个子集的异或和都不同且不为 $0$，而线性基外任意一个子集异或和都可以用线性基内的一个子集来表示

模板

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
struct LinearBasis {
    static const int n = 60;
    bool O; ll a[n + 1]; int cnt;

    void clear() { O = 0; cnt = 0; for (int i = 0; i <= n; ++i) a[i] = 0; } 
    void insert(ll v) {
        for (int i = n; ~i; --i) {
            if (!(v >> i & 1)) continue;
            if (!a[i]) { a[i] = v; break; }
            v ^= a[i]; 
        } O |= !v; 
    }
    void work() {
        for (int i = 0; i <= n; cnt += a[i++] > 0)
            for (int j = 0; j < i; ++j)
                if (a[i] >> j & 1) a[i] ^= a[j];
    }
    ll get_max(ll v = 0) {
        for (int i = n; ~i; --i) v = max(v, v ^ a[i]); 
        return v;
    }
    ll get_min() {
        if (O) return 0;
        for (int i = 0; i <= n; ++i)
            if (a[i]) return a[i];
    }
    ll get_min(ll v) {
        for (int i = n; ~i; --i) v = min(v, v ^ a[i]);
        return v;
    } 
    ll get_kth(ll k) {
        ll ans = 0; k -= O; 
        for (int i = 0; i <= n; ++i) {
            if (!a[i]) continue;
            if (k & 1) ans ^= a[i];
            k >>= 1; 
        }
        if (k > 0) return -1; 
        else return ans; 
    }
    bool check(ll v) {
        for (int i = n; ~i; --i) {
            if (!(v >> i & 1)) continue;
            if (!a[i]) return 0;
            v ^= a[i]; 
        } return 1;
    } 
} S;

区间线性基

我们注意到平时写的一般的线性基在插入的时候，$a[i]$ 所存储的值总是最靠左的那个

现在我们考虑维护每一个前缀线性基，但是 $a[i]$ 存储的值是最靠右的那一个

我们只需要对 $insert$ 稍做修改即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct LinearBasis {
    static const int n = 30;
    int a[n + 1], p[n + 1]; 

    void insert(int k, int v) {
        for (int i = n; ~i; --i) {
            if (!(v >> i & 1)) continue;
            if (!a[i]) { a[i] = v; p[i] = k; break; }
            if (k > p[i]) swap(a[i], v), swap(p[i], k);
            v ^= a[i]; 
        }
    }
    int get_max(int k) {
        int v = 0; 
        for (int i = n; ~i; --i)
            if (p[i] >= k) v = max(v, v ^ a[i]);
        return v;
    }
} S;

例题

hdu 6579 Operation