C.幼稚國王的獎賞

https://tioj.ck.tp.edu.tw/problems/1094

Description

定義一個非負整數集合的價值是裡面所有數字XOR起來
給定一些非負整數，問你能選出價值最高的子集價值是多少？

Solution

經典題 maximum subset xor

線性基

首先可以把每個數字的二進位看成模2的$k$維向量

span

我們說一群向量$S = {\textbf{v}_ 1, \textbf{v}_ 2, \dots, \textbf{v}_ n}$的線性生成空間是

$$
\textrm{span}(S) = { \sum _ {i=1}^n\lambda _ i \textbf{v} _ i }
$$

也就是說$\textrm{span}(S)$代表的是所有$S$內的元素的有限線性組合

linear independent

對於一組向量${\textbf{v}_ 1, \textbf{v}_ 2, \dots, \textbf{v} _ n}$
若存在不全為$0$的$\lambda_1, \lambda_2, \dots, \lambda_n$使得
$$
\sum _ {i=1}^n\lambda_ i \textbf{v}_ i = \textbf{0}
$$
則我們說這群向量是線性相關的；反之則稱為線性獨立(linear independent)

一組線性相關的向量至少有一個向量可以用其他向量表示
說明: 不失一般性設$\lambda _ 1 \neq 0$，則
$$
\textbf{v} _ 1 = \sum _ {i=2}^n \frac{-\lambda _ i}{\lambda _ 1} \textbf{v} _ i
$$

basis

一組向量$B={\textbf{e}_ 1, \textbf{e}_ 2, \dots, \textbf{e}_ n}$是一個向量空間$V$的基底(basis)若且唯若$\textrm{span}(B) = V$且$B$是一組線性獨立的向量

由定義可以直接推出，$V$中的所有向量$\textbf{v}$都可以唯一表示為$B$裡面的向量的線性組合，因為

$$
\textbf{v} = \sum \lambda_ i \textbf{e}_ i = \sum \lambda_ i’ \textbf{e}_ i \Leftrightarrow \sum (\lambda_ i - \lambda_ i’) \textbf{e}_ i = \textbf{0} \Leftrightarrow \forall i, \lambda_ i = \lambda_ i'
$$

高斯消去

講了那麼多廢話，這題到底要怎麼做呢？
設給定的數字集合是$V$，可以發現我們要求的就是$S = \textrm{span}(V)$中的最大值，透過維護$S$的基底集合$B$，我們能夠快速得知是否能夠湊出一個第k位是1的XOR值

當我們考慮到第k位的時候，我們至多只需要保存一個最高位是第k位的基底，因為假設有兩個基$x,y$其第k位都是1，則可以用$x \oplus y$來代替$x$

嘗試加入一個數字$x$到基底時，我們從$x$的最高位k開始看
假設已經有一個基底$e$的最高位是第k位，我們就可以把$x$替換成$x \oplus e$，如果此時$x$變為0代表$x$已經可以用前面的一些基底湊出來了，加入$x$會破壞線性獨立的特性；
反之，若沒有一個基底$e$的最高位是第k位，那我們就直接加入$x$作為提供第k位的1的人

那麼最後我們要怎麼取最大值呢？同樣從最高位開始看
如果目前看到第k位，並且答案的第k位是0
若又剛好存在一個最高位是第k位的基底$e$的話，我們取$e$肯定不會虧嘛
因為$e$是我們維護唯一一個最高位是第k位的基底，之後不會再考慮到第k位以上的東西了

如果上面的東東聽不懂的話就努力看code參透吧QQ

AC code

 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

#include <bits/stdc++.h>

using namespace std;

const int K = 20;

int n,v;
int bas[K];
void ins(int x) {
    for(int i = K-1; i >= 0; i--) if(x & (1<<i)) {
        if(bas[i]) x ^= bas[i];
        else {
            bas[i] = x;
            break;
        }
    }
}
int getmax() {
    int res = 0;
    for(int i = K-1; i >= 0; i--) {
        if((res ^ bas[i]) & (1<<i)) res ^= bas[i];
    }
    return res;
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    while(cin >> n && n) {
        for(int i = 0; i < K; i++) bas[i] = 0;
        for(int i = 0; i < n; i++) {
            cin >> v;
            ins(v);
        }
        cout << getmax() << '\n';
    }
}