Acwing 3164. 线性基

这里推荐 Acwing 上的线性基模板。luogu 上的模板数据范围太小了。

这里的求线性基是求一种特殊的线性基：把每个数在二进制下的每一位看做一个 0/10/1 分向量，每个数表示一个向量，一个数组就是一个向量组。求这个向量组的线性基。

1. 高消法

生成的线性基拥有的性质：

  1. 是原向量组的线性基废话

  2. 线性基内所有数在二进制下会构成上三角结构（重要性质）

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 1e5;
const int MAXm = 64;

template <typename T>
inline void read(T &a) {
    char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
    read(a), read(argv...);
}

inline bool deg(int num, int deg) {
    return num & (1ll << deg);
}
int n;
int a[MAXn + 10];
signed main() {
    read(n);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    int row = 1;
    for (int col = MAXm - 1; ~col && row <= n; --col) {
        for (int i = row; i <= n; ++i) {
            if (deg(a[i], col)) {
                swap(a[row], a[i]);
                break;
            }
        }
        if (!deg(a[row], col)) continue;
        for (int i = 1; i <= n; ++i) {
            if (i == row) continue;
            if (deg(a[i], col)) {
                a[i] ^= a[row];
            }
        }
        ++row;
    }
    int ans = 0;
    for (int i = 1; i < row; ++i) {
        ans ^= a[i];
    }
    printf("%lld\n", ans);
    return 0;
}

提供一组样例：

1
2
10
681519689123291 153992348230057 352917520953222 379410980430607 333284887124912 596782649548897 1004880543767517 258503666829624 353486948696275 244563245470691

二进制表示：

1
2
3
4
5
6
7
8
9
10
10011010111101011010101010111110100100010111011011
00100011000000111000100011001101101110000110101001
01010000001111101000000011011110001010111110000110
01010110010001001010000000101101100110001100001111
01001011110001111011101111010011100101101110110000
10000111101100010101001001110101011010000001100001
11100100011110111011111011110110100101101111011101
00111010110001101110010011001111000000100100111000
01010000010111111010011000000000101000000011010011
00110111100110110111010001010111110001001111100011

生成的线性基：

1
2
3
4
5
6
7
8
9
10
10000001000011001001000110110011001011000111101101
01000000000011101000011101111011101100011100010000
00100001000101101011000000110100000110101011111001
00010000000110010110100001010011001111111101100001
00001001000110111110011101100100011100101011110101
00000100000011100011111011010100100110100010001100
00000010000101010011100011111001101000101101010000
00000000100011111010101000011101110110010110100111
00000000010010000100100100101000001011100010100010
00000000001010010110111111110110101001011111110111

可以看到确实是上三角结构。

2. 贪心法

生成的线性基不具有性质 2。

所以这种方法生成的线性基不能处理一些问题。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 1e5;
const int MAXm = 64;

template <typename T>
inline void read(T &a) {
    char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
    read(a), read(argv...);
}

inline int degll(int num, int deg) {
    return num & (1ll << deg);
}
inline int maxdegll(int num) {
    return 63 - __builtin_clzl(num);
}

int n;
int num[MAXm + 10];
signed main() {
    read(n);
    for (int i = 1, a, mxdeg; i <= n; ++i) {
        read(a);
        while (a) {
            mxdeg = maxdegll(a);
            if (num[mxdeg]) {
                a ^= num[mxdeg];
            } else {
                num[mxdeg] = a;
                break;
            }
        }
    }
    int ans = 0;
    for (int i = MAXm - 1; ~i; --i) {
        if (!degll(ans, i)) {
            ans ^= num[i];
        }
    }
    printf("%lld\n", ans);
    return 0;
}

生成的线性基：

1
2
3
4
5
6
7
8
9
10
10011010111101011010101010111110100100010111011011
01010000001111101000000011011110001010111110000110
00100011000000111000100011001101101110000110101001
00011011111110010011101100001101101111010000110110
00001101101100110001110001011011100101000000101001
00000110011110100010000011110011101100110010001001
00000010001111000101011100001111000001110010100111
00000000110001111110001100110101111101110100000101
00000000011000010010011011011110100010111101010101
00000000001010010110111111110110101001011111110111

而且注意这种方法生成的线性基存在 num 数组里的时候不是连续的，如果删去 41 行 if (!degll(ans, i)) 的话输出的是：

1
2
3
4
5
6
7
8
9
10
11
10011010111101011010101010111110100100010111011011
01010000001111101000000011011110001010111110000110
00100011000000111000100011001101101110000110101001
00011011111110010011101100001101101111010000110110
00001101101100110001110001011011100101000000101001
00000110011110100010000011110011101100110010001001
00000010001111000101011100001111000001110010100111
00000000000000000000000000000000000000000000000000
00000000110001111110001100110101111101110100000101
00000000011000010010011011011110100010111101010101
00000000001010010110111111110110101001011111110111