ACM►数学►线性基

线性基小结

感谢

Sengxian’s Blog

前言

感觉 Sengxian 的博客里面写的太好了，然后这里只打算添加一下自己的理解了。

首先所谓的线性基，就是把若干个整数，看成 n 维 01 向量（通常 n 不会超过 64，即 long long 的范围），然后求这些向量的一个极大无关组。需要注意的一点是，对于这里的 01 向量，只有异或运算。

不过一般为了方便处理，我们会把极大无关组进行列变换化最简形。一个向量空间可以有多个基，但是化为最简形后基是唯一的。化为最简形后和原来是等价的，由化最简形后的向量组可以表示的向量都可以由原向量组来表示。

下面是利用高斯消元求解线性基的代码，由 Sengxian 的代码改过来的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void cal(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = MAX_BASE; j >= 0; j--) {
            if (data[i] >> j & 1) {
                if (b[j]) data[i] ^= b[j];
                else {
                    b[j] = data[i];
                    for (int k = j - 1; k >= 0; k--) if (b[k] && b[j] >> k & 1) b[j] ^= b[k];
                    for (int k = j + 1; k <= MAX_BASE; k++) if (b[k] >> j & 1) b[k] ^= b[j];
                    break;
                }
            }
        }
    }
}

SGU-275

给出 N 个数，求 N 个数异或可以得到的最大值，数的范围在 long long 内。

求出线性基，然后异或就是答案，这里 Sengxian 博客有证明，不过这里补充一点，对于上面算法得到的线性基是唯一的。

AC代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX_BASE = 63;

ll b[200];
ll a[11234];

void cal(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = MAX_BASE; j >= 0; j--) {
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for (int k = j - 1; k >= 0; k--) if (b[k] && b[j] >> k & 1) b[j] ^= b[k];
                    for (int k = j + 1; k <= MAX_BASE; k++) if (b[k] >> j & 1) b[k] ^= b[j];
                    break;
                }
            }
        }
    }
}

int main() {
    int n;
    while (~scanf("%d", &n)) {

        memset(b, 0, sizeof(b));
        for (int i = 0; i < n; i++) {
            scanf("%lld", a + i);
        }
        cal(n);
        ll ans = 0;
        for (int i = 0; i <= MAX_BASE; i++) {
            if (b[i] >> i & 1) ans ^= b[i];
        }
        printf("%lld\n", ans);
    }

}

CF-895C

给出 N 个数的集合，问能取出多少不同的子集，使得乘积是平方数。输入的数字小于 70 。

对平方数进行质因数分解，会发现每个质因子的幂都是偶数。现在对输入的 N 个数进行质因数分解，对每个质因子只对它的幂的奇偶性有关，可以计算小于 70 的质因子只有 20 个，那么我们用一个 01 变量来表示每个数质因子奇偶性的情况。

然后我们对这 N 个 01 向量求线性基，那么答案就是 $2^{N - BaseSize} - 1$，注意线性基其实就是选了若干个线性无关的向量并且化简后的结果。这时候对于没有选中的向量，取任意子集，异或得到的向量都可以由线性基基来表示，总共有上面答案数的子集（减去了空集）。对于线性基选中的向量，因为是线性无关，所以不能互相表示，不贡献答案。

AC代码

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX = 112345;
const int MOD = 1e9 + 7;
const int MAX_BASE = 20;

bool now_prime[200];

vector<int> primes;

void get_primes() {
    for (int i = 2; i <= 70; i++) {
        if (now_prime[i]) continue;
        primes.push_back(i);
        for (int j = i * 2; j <= 70; j += i) {
            now_prime[j] = true;
        }
    }
}

int raw_data[MAX];
int data[MAX];

int solve(int n) {
    int rst = 0;
    for (int i = 0; i < primes.size(); i++) {
        while (n % primes[i] == 0) {
            rst ^= (1 << i);
            n /= primes[i];
        }
    }
    return rst;
}

int b[200];

void cal(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = MAX_BASE; j >= 0; j--) {
            if (data[i] >> j & 1) {
                if (b[j]) data[i] ^= b[j];
                else {
                    b[j] = data[i];
                    for (int k = j - 1; k >= 0; k--) if (b[k] && b[j] >> k & 1) b[j] ^= b[k];
                    for (int k = j + 1; k <= MAX_BASE; k++) if (b[k] >> j & 1) b[k] ^= b[j];
                    break;
                }
            }
        };
    };
}

int pow_mod(ll a, int k) {
    ll rst = 1;
    while (k) {
        if (k & 1) rst = rst * a % MOD;
        a = a * a % MOD;
        k >>= 1;
    }
    return (int)rst;
}

int main() {
    get_primes();
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", raw_data + i);
        data[i] = solve(raw_data[i]);
    }
    cal(n);
    int cnt = 0;
    for (int i = 0; i <= MAX_BASE; i++) {
        if (b[i]) cnt++;
    }
    printf("%d\n", (pow_mod(2, n - cnt) - 1 + MOD) % MOD);
}