向量空間與 Xor Basis

由於最近學校也學到「向量空間」這個概念，決定重新來了解 Xor Basis (在對岸稱為線性基) 的概念，並將這些概念記錄下來

以下會有很多的定義，而且這個概念也很抽象，不過我也不知道怎麼解釋得更簡單

向量空間 (Vector Space)

首先我們要先認識「向量空間」是什麼，基本上都是定義，與大家以前學的向量的性質有關

不過在向量空間中的向量不見得會是我們所熟知的向量，也可能是函數、多項式等等

定義

對於一個集合 \(S\)，定義兩種運算「向量加法」與「純量乘法」

只要滿足以下十個條件，這個集合 \(S\) 即為「向量空間」

加法	乘法
1.\(u+v \in S\) (封閉性)	6.\(cv \in S\) (封閉性)
2.\((u+v)+w = u+(v+w)\) (結合律)	7.\(c(u+v) = cu+cv\) (結合律)
3.\(u+v = v+u\) (交換律)	8.\((uv)w=u(vw)\) (交換律)
4.\(u + 0 = u\) (有加法單位元)	9.\(1 \cdot v= v\) (有乘法單位元)
5.\(u+(-u)=0\) (有加法反元素)	10.\((a+b)v = av+bv\) (分配律)

常見的向量空間

\((x_1,x_2,\cdots,x_n)\)，可以是 \(\mathbb{R}^n, \mathbb{Z}^n\) 等等
\(n \times m\) 維矩陣
度數 \(\le n\) 的多項式
\(f(x), g(x)\)，加法 \((f+g)(x)\)，乘法 \(cf(x)\)

這些都可以很輕易地驗證以上 10 種性質，因此他們都是向量空間

接著向量空間有很多的名詞，因此我們要先了解這些名詞的定義

線性組合 (Linear Combination)

定義

對於一個 \(n\) 個向量 \(v_1, v_2, \cdots, v_n\)，\(c_i\) 為純量，這些向量的線性組合可以寫成向量

\[x = c_1v_1+c_2v_2+\cdots+c_nv_n\]

範例

在 \(\mathbb{R}^2\) 的空間中，\((3,4)\) 可以寫成 \((1,0),(0,1)\) 的線性組合，\((3,4) = 3(1,0) + 4(0,1)\)
在 \(\mathbb{R}^3\) 的空間中，\((1,2,3)\) 可以寫成 \((1,1,0),(0,1,1),(1,0,1)\) 的線性組合，\((1,2,3) = 0(1,1,0)+2(0,1,1)+1(1,0,1)\)

生成空間 (Span)

定義

當一個向量空間 \(V\) 被一個集合 \(S\) Span，則任意一個 \(u \in V\) 都可以寫成 \(S\) 當中的向量的線性組合，意即 \(u = c_1v_1+c_2v_2+\cdots+c_nv_n\)。我們將 \(V\) 記為 \(span(S)\)，而 \[span(S) = \{\sum_{i=1}^nc_iv_i\}\]

一個特點是對於任何一個包含 \(S\) 的向量空間 \(U\), \(span(S) \subset U\)

範例

1.當 \(S = \{(1,0),(0,1)\}\) 時，\(span(S)\) 包含所有 \(\mathbb{R}^2\) 空間中的向量，因為任一向量 \((x_1,x_2)\) 皆可寫成 \((x_1,x_2)=x_1(1,0)+x_2(0,1)\) 2.當 \(S = \{(1,1),(1,-1)\}\)時，\(span(S)\) 包含所有 \(\mathbb{R}^2\) 空間中的向量，因為任一向量 \((x_1,x_2)\) 皆可寫成 \((x_1,x_2)=\frac{x_1+x_2}{2}(1,1)+\frac{x_1-x_2}{2}(1,-1)\)

線性獨立 (Linearly Independent)

定義

對於 \(n\) 個向量 \(\{v_1,v_2,\cdots,v_n\}\)，滿足

\[c_1v_1+c_2v_2+\cdots+c_nv_n = 0\]

只有 \(c_1=c_2=\cdots = 0\) 的解，則我們稱這些向量線性獨立

線性相依 (Linearly Dependent)

定義

對於 \(n\) 個向量 \(\{v_1,v_2,\cdots,v_n\}\)，滿足

\[c_1v_1+c_2v_2+\cdots+c_nv_n = 0\]

存在 \(c_i\) 不全為 \(0\) 的解，則我們稱這些向量線性相依

定理

一個集合 \(S\) 線性相依 \(\Leftrightarrow\) 其中一個向量可以寫成其他向量的線性組合

證明

(\(\Rightarrow\)): 如果集合 \(S\) 線性相依，則其中一個向量可以寫成其他向量的線性組合

根據線性相依的定義，\(c_1v_1+c_2v_2+\cdots+c_nv_n = 0\) 有一組非全零的解

我們可以不失一般性的假設 \(c_1 \ne 0\)，得到

\[v1 + c_2v_2 +\cdots+c_nv_n = 0\]

移項得到

\[c_2v_2 +\cdots+c_nv_n = -v_1\]

(\(\Leftarrow\)): 如果集合 \(S\) 中其中一個向量可以寫成其他向量的線性組合，則集合 \(S\) 線性相依

假設集合 \(S\) 其中一個向量可以寫成其他向量的線性組合

我們可以不失一般性的假設 \(v_1\) 可以寫成 \(v_2,\cdots,v_n\) 的線性組合

\[v_1 = c_2v_2+c_3v_3+\cdots+c_nv_n\]

移項得到

\[v_1-c_2v_2-c_3v_3-\cdots-c_nv_n = 0\]

為一組係數不全為 \(0\) 的解

基底 (Basis)

定義

對於一個向量空間 \(V\)，如果找的到一個集合 \(S\) 滿足

\(span(S) = V\)
\(S\) 線性獨立

則稱 \(S\) 為 \(V\) 的基底

而任何 \(V\) 當中的向量都可以寫成唯一一組 \(S\) 的線性組合

一個向量的基底可以有很多個
對於任何一個 \(V\) 的基底，大小皆相同，我們將 \(V\) 的基底大小寫成 \(dim(V)\)

XOR 與 \(\mathbb{Z}^d_2\)

對於 XOR 這個運算，當 \(x,y \in \{0,1\}\) 時，\(x \oplus y = x+y \pmod{2}\)

而任何一個數字，我們皆可以將其換為二進位的形式

如: \(5 = (101)_2\), \(3 = (011)_2\)

因此我們可以定義向量空間 \(\mathbb{Z}^d_2\)

加法運算為 \(x+y \pmod{2}\) 等價於 XOR，純量乘法的 \(c_i \in \{0,1\}\)

藉由這樣的定義，我們就可以藉由向量空間的性質來處理 XOR 的問題了

如何對一組數字找到 XOR Basis

最簡單的方式為 高斯消去法，我們可以將數字寫成二進位，並將所有的向量放到矩陣上，進行 高斯消去法，消成列梯形矩陣 (row-echelon form)，非零向量的集合即為這組數字的 XOR Basis

範例

找到 \(\{3,5,6\}\) 的 XOR Basis

將 \(3,5,6\) 寫成 \(\{0,1,1\}, \{1,0,1\}, \{1,1,0\}\) 放到矩陣上進行高斯消去

\[\begin{bmatrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0\end{bmatrix} \rightarrow \begin{bmatrix}1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1\end{bmatrix} \rightarrow \begin{bmatrix}1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1\end{bmatrix} \rightarrow \begin{bmatrix}1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0\end{bmatrix}\]

則 \(\{(011)_2, (110)_2\} = \{3,5\}\) 為 \(\{3,5,6\}\) 的基底

而 \(\dim(\{3,5,6\})\) 即為 \(2\)

找到 \(\{1,5,4\}\) 的 XOR Basis

將 \(1,5,4\) 寫成 \(\{0,0,1\}, \{1,0,1\}, \{1,0,0\}\) 放到矩陣上進行高斯消去

\[\begin{bmatrix}0 & 0 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 0\end{bmatrix} \rightarrow \begin{bmatrix}1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 1\end{bmatrix} \rightarrow \begin{bmatrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1\end{bmatrix} \rightarrow \begin{bmatrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0\end{bmatrix}\]

則 \(\{(100)_2, (001)_2\} = \{4,1\}\) 為 \(\{1,5,4\}\) 的基底

而 \(\dim(\{3,5,6\})\) 即為 \(2\)

程式中的實作

在實作上，當我們處理的位數很少時，我們通常不會直接使用高斯消去法，反之，以下為兩種常見的寫法

枚舉每個 bit

這個寫法類似高斯消去的想法，當我們在加入一個向量 \(v\) 時，我們檢查他的每個 bit，如果當前的基底中在這個 bit 有向量 \(b\) 的話，我們就將 \(v\) 減去 \(b\)，之後再繼續檢查能不能加入，直到當前的基底中不含有某個 bit 時，我們就將 \(v\) 加入基底，並跳出迴圈。

如果要檢查當前的基底是否能線性組合出 \(v\)，方法也很類似

時間複雜度: \(O(\log C)\) 插入

void add_vector(int x){
    for(int i = LOGN; i >= 0;i--){
        if(x&(1<<i)){
            if(!basis[i]){
                basis[i] = x; 
                sz++; //增加基底大小
                return;
            }
            x ^= basis[i];
        }
    }
}

bool check(int x){
    for(int i = LOGN; i >= 0;i--){
        if(x&(1<<i)){
            if(!basis[i]) return false;
            x ^= basis[i];
        }
    }
    return true;
}

枚舉基底

這個寫法是我個人比較喜歡的寫法，同樣與高斯消去法很相似，我們每次判斷一個向量能不能加入基底時，我們就用 xor 的方式去試著消，如果最後這個向量被消為 \(0\) 了，則表示這個向量與基底不是線性獨立的，否則我們就可以將其加入基底

時間複雜度: \(O(\log C)\) 插入

vector<int> basis;
void add_vector(int x){
    for(auto v : basis){
        x = min(x,x^v);
    }
    if(x!=0) basis.push_back(x);
}

bool check(int x){
    for(auto v : basis){
        x = min(x,x^v);
    }
    return x == 0;
}

所以 XOR Basis 能幹嘛?

以下是一些我們常會見到的線性基可以使用的地方

給你一個數字集合 \(S = \{a_1,a_2,\cdots,a_n\}\)，問這些數字能不能夠 XOR 出 \(x\)

找到 \(S\) 的 XOR Basis 之後，再去檢查 \(x\) 是否能被基底線性組合而成即可。

給你一個數字集合 \(S = \{a_1,a_2,\cdots,a_n\}\)，問這些數字可以 XOR 出多少數字

既然我們想要知道能夠 XOR 出多少數字，就是問 \(span(S)\) 的大小，因此我們只要找到 \(S\) 的 XOR Basis \(V = \{x_1,x_2,\cdots,x_k\}\)，我們知道這些數字可以組成 \(u = c_1x_1+c_2x_2+\cdots+c_kx_k\)，而 \(c_i \in \{0,1\}\)，所以這個數字集合能夠 xor 出的數字數量即為 \(2^k\)。

給你一個數字集合 \(S = \{a_1,a_2,\cdots,a_n\}\)，問這些數字可以 XOR 出的第 \(k\) 大的數字

我們找到 XOR Basis 之後，再去枚舉 bit 就可以找到可以 span 出的第 \(k\) 大的數字了

給你一個數字集合 \(S = \{a_1,a_2,\cdots,a_n\}\)，問這些數字可以 XOR 出的最大的數字

這個有個很簡單的寫法，不論是第一種還是第二種 xor basis 都可以用這個方式計算

//第一種的找法
int get_mx(){
    int ans = 0;
    for(int i = LOGN; i >= 0;i--){
        ans = max(ans,ans^basis[i]);
    }
}

//第二種的找法
int get_mx(){
    int ans = 0;
    for(auto v : basis){
        ans = max(ans,ans^v);
    }
}

接著，讓我們正式來看看一些例題吧

例題

CSAcademy - XOR Closure

題目連結

你有一個 \(n\) 個數字的集合 \(S\)，你最少要加入幾個數字，才能使得對於任意兩個 \(S\) 中的元素 \(x,y\)，\(x \oplus y\) 也在集合 \(S\) 當中

因為所有元素的線性組合都要在集合 \(S\) 當中，我們只要找到 \(span(S)\) 的大小減去 \(n\) 即為答案，因此我們只要對 \(S\) 找到 XOR Basis，答案即為 \(2^{\text{size of basis}}-n\)

程式碼

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

signed main(){
    fastio
    int n;
    cin >> n;
    
    vector<int> basis;
    for(int i = 0;i < n;i++){
        int x;
        cin >> x;
        for(auto y : basis) 
            x = min(x, x^y);
        if(x) basis.push_back(x);
    }

    cout << (1LL<<basis.size())-n << "\n";
}

Codeforces 895C - Square Subsets

題目連結

你有 \(n\) \((n \le 10^5)\) 個數字 \(a_1,\cdots,a_n\) (\(a_i \le 70\))，你想要知道這些數字有幾個非空子集的乘積是一個完全平方數

首先，觀察到 \(a_i\) 的範圍很小，只有到 \(70\)，而小於 \(70\) 的質數總共只有 \(19\) 個，因此我們考慮位元 DP

設 \(dp[i][mask]\) 為考慮所有小於 \(i\) 的數字，有幾個子集的乘積的為 \(mask\)，接著我們就能在 \(O(70 \times 2^{19})\) 的時間計算完答案了

欸等等，跟 XOR Basis 有什麼關係阿?

我們可以觀察到，其實題目想要詢問的東西是總共有幾個方式可以從數字集合中 span 出 \(0\)，因此其實我們只要對題目的數字進行轉換之後，找到 XOR Basis，答案就會是 \(2^{n-\text{size of basis}}-1\)，我們就能在 \(O(n \times 19)\) 的時間找到答案了，比位元 DP 還快。

而且就算 \(a_i\) 的值域變得更大，我們也能使用 XOR Basis 進行計算

程式碼

Codeforces 959F - Mahmoud and Ehab and yet another xor task

題目連結

你有一個 \(n\) 個數字的陣列 \(a_1,a_2,\cdots,a_n\)，接著有 \(q\) 次詢問，每次詢問前 \(l\) 個數字有幾種方法可以 xor 湊出 \(x\)

首先，我們可以很直接地想到，既然我們想要知道有幾種方法可以湊出 \(x\)，那麼一定與前 \(i\) 個數字的 span 有關

我們可以想到，如果我們先將輸入依照 \(l\) 排序好，接著我們只要照順序將數字加進集合中，找到集合的 XOR Basis

如果我們的基底不能夠線性組合出 \(x\)，則答案為 \(0\)，否則我們有 \(2^{\text{l-size of basis}}\) 種湊出 \(x\) 的方式

CSAcademy - XOR Cycle

給你一張 \(n\) 個點 \(m\) 條邊的連通圖，問封閉迴路的邊權 XOR 出的最大值為多少?

在寫這題以前，推薦可以先去寫這題

首先，我們藉由 Cycle Basis，我們可以知道任何封閉迴路皆可以由簡單環所組成，因此我們只要對所有簡單環 XOR 出來的答案找到 XOR Basis，接著再找到這個 XOR Basis 可以 span 出的最大數字即為答案。

程式碼

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e5+5;
vector<pair<int,int>> adj[N];
int dsu[N], dep[N], vis[N];

int find(int u){
    return dsu[u]==u ? u : dsu[u] = find(dsu[u]);
}

bool unite(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return false;
    dsu[u] = v;
    return true;
}

void dfs(int u, int p){
    for(auto [v,w] : adj[u]){
        if(v == p) continue;
        dep[v] = dep[u]^w;
        dfs(v, u);
    }
}

signed main(){
    fastio
    int n,m;
    cin >> n >> m;

    vector<pair<pair<int,int>,int>> edges;
    iota(dsu,dsu+N,0);

    for(int i = 0;i < m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        if(unite(u,v)) adj[u].push_back({v,w}), adj[v].push_back({u,w});
        else edges.push_back({{u,v},w});
    }

    dfs(1,-1);

    vector<int> basis;

    for(auto [p,w] : edges){
        auto [u,v] = p;
        int x = dep[u] ^ dep[v] ^ w;
        for(auto y : basis) x = min(x, x^y);

        if(x) basis.push_back(x);
    }

    int ans = 0;
    for(auto x : basis) ans = max(ans, ans^x);
    cout << ans << "\n";

}

ABC223H - Xor Query

題目連結

給你一個 \(n\) 個數字的陣列，接著有 \(q\) 個詢問，每次詢問區間 \([l,r]\) 是否能經由 xor 湊出 \(x\)

這個的想法就是很直接的維護 \([l,r]\) 的線性基，我們可以使用線段樹等資料結構來維護區間數字 xor basis，每次再去檢查這個 basis 是否能線性組合出 \(x\) 即可。

沒想到在線性代數中所學到的「向量空間」在競程上也有它的應用呢

而 XOR 真的是一個很神奇的運算，能夠放到 trie 上面處理，也能藉由向量空間的基底去計算答案

參考資料

https://codeforces.com/blog/entry/68953

https://zhuanlan.zhihu.com/p/68575986

向量空間 (Vector Space)

定義

常見的向量空間

線性組合 (Linear Combination)

定義

範例

生成空間 (Span)

定義

範例

線性獨立 (Linearly Independent)

定義

線性相依 (Linearly Dependent)

定義

定理

證明

基底 (Basis)

定義

XOR 與 \(\mathbb{Z}^d_2\)

如何對一組數字找到 XOR Basis

範例

找到 \(\{3,5,6\}\) 的 XOR Basis

找到 \(\{1,5,4\}\) 的 XOR Basis

程式中的實作

枚舉每個 bit

枚舉基底

所以 XOR Basis 能幹嘛?

給你一個數字集合 \(S = \{a_1,a_2,\cdots,a_n\}\)，問這些數字能不能夠 XOR 出 \(x\)

給你一個數字集合 \(S = \{a_1,a_2,\cdots,a_n\}\)，問這些數字可以 XOR 出多少數字

給你一個數字集合 \(S = \{a_1,a_2,\cdots,a_n\}\)，問這些數字可以 XOR 出的第 \(k\) 大的數字

給你一個數字集合 \(S = \{a_1,a_2,\cdots,a_n\}\)，問這些數字可以 XOR 出的最大的數字

例題

CSAcademy - XOR Closure

Codeforces 895C - Square Subsets

Codeforces 959F - Mahmoud and Ehab and yet another xor task

CSAcademy - XOR Cycle

ABC223H - Xor Query

更多練習題

AGC045A - Xor Battle

Codeforces 1427E - Xum

Codeforces 1336E1 - Chiori and Doll Picking (easy version)

更多題目待補

心得

參考資料