線性基筆記 & 一些XOR問題

Created2021-02-06Updated2021-02-06

參考資料：Here, Here

第一次打這種筆記，打得不好請見諒> <

線性基

線性基通常被用來處理奇怪xor的問題
線性基BB為一個整數集合AA的子集，需滿足以下條件：

  1. 不存在一個subset的xor值為0
  2. 能由AA的subset算出來的xor值，也能透過BB的某個subset算出來

若我們把一個數二進位分解後，將他視為一個向量
像是4=(0,0,1,0,0),23=(1,0,1,1,1)4 = (0, 0, 1, 0, 0), 23 = (1, 0, 1, 1, 1)
用線代的觀點來看就是「任兩向量線性獨立」和「BB可以張成AA」

那要如何蓋出現線性基呢？直接先上code

1
2
3
4
5
6
7
8
9
10
11
int basis[30];

void add(int x) {
    for (int i = 29; ~i; --i) if (x >> i & 1) {
        if (!basis[i]) {
            basis[i] = x;
            return;
        }
        x ^= basis[i];
    }
}

basis[i]所代表的意義為：high bit為ii的一組basis
而在加入的時候，會從最大的bit開始看，若該bit為1且目前還沒有basis的存在，就保證他與其他basis線性獨立，因此直接加入
否則就把他與basis[i]xor，讓當前的bit回到0，繼續跑下去

這裡我講得較簡略，參考資料第二個連結的CF文章有較詳細的敘述

這樣就完成線性基的加入操作，複雜度為O(logC)\mathcal{O}(logC)
以下將講一些題目與其應用

CF - 845G

連結

題意

給一張nn個點mm條邊的連通無向帶權圖，定義一條路徑的權重為路徑上所有邊權的xor和，請求11到nn的最小路徑

(1≤n≤100000,1≤m≤100000)(1 \leq n \leq 100000, 1 \leq m \leq 100000)

作法

首先，所有可能的權重會是11到nn其中一條路徑權重和圖上一些環的xor，
很顯然的解釋方法是一條邊來回走一遍的話會是0，所以要讓權重改變一定要經過環

再來的問題就會變成如何找出圖上的環了，以11為根做dfs樹，定義did_i為經由父邊從11走到ii的xor值，則每走到一條回邊(u,v)(u, v)就代表找到一個權重為du⊕dv⊕w(u,v)d_u \oplus d_v \oplus w(u, v)的環

這樣跑完就可以找到所有環了…嗎？
因為xor的性質，圖上任一一個環一定可以表示成數個生成樹環的xor值，所以這是對的

之後對那些環建好線性基，之後就可以採取greedy的方式，從高位開始取
然後順者做完一遍就結束了

複雜度是好好的O(nlogC)\mathcal{O}(nlogC)

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
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
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 998244353, abc = 864197532, N = 100002, logN = 17, K = 333;

int basis[30];

void add(int x) {
    for (int i = 29; ~i; --i) if (x >> i & 1) {
        if (!basis[i]) {
            basis[i] = x;
            return;
        }
        x ^= basis[i];
    }
}

vector <pii> adj[N];
int dis[N];
bool vis[N];

void dfs(int v, int pa, int W) {
    dis[v] = ~pa ? dis[pa] ^ W : 0;
    vis[v] = true;
    for (auto [u, w] : adj[v]) if (u != pa) {
        if (vis[u]) {
            add(dis[v] ^ dis[u] ^ w);
        } else {
            dfs(u, v, w);
        }
    }
}


int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0, u, v, w; i < m; ++i) {
        cin >> u >> v >> w, --u, --v;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }
    dfs(0, -1, 0);
    int ans = dis[n - 1];
    for (int i = 29; ~i; --i) if (ans >> i & 1) {
        if (basis[i]) ans ^= basis[i];
    }
    cout << ans << endl;
}

CF - 959F

連結

題意

有一個長度為nn的序列，有qq筆詢問，每筆給你l,xl, x問由陣列前ll項組成的subset有幾個的xor值為xx

(1≤n,q≤100000)(1 \leq n, q \leq 100000)

作法

假設現在的問題是l=nl = n，要怎麼處理這個問題？
先給出結論：

  1. 若該子集湊不出xx，則答案為0
  2. 否則答案為2n−∣B∣2^{n - |B|}

1很trivial，2的話因為線性基的性質，那∣B∣|B|個向量湊的出所有可能的xor值，那麼另外2n−∣B∣2^{n - |B|}個子集一定可以用另外∣B∣|B|個向量湊出xx

雖然不怎麼直觀，但事實上只要湊得出來，任何xx的答案都是一樣的

這樣一來原本的問題就簡單了，首先先把詢問離線排序，按照ll排好
之後只要一一加入向量，對每筆詢問判斷能否湊出xx，就可以直接計算出答案了

複雜度也是好好的O((n+q)logC)\mathcal{O}((n + q)logC)

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
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
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 400008, logN = 17, K = 333;

int basis[20];

bool add(int x) {
    for (int i = 19; ~i; --i) if (x & (1 << i)) {
        if (!basis[i]) {
            basis[i] = x;
            return true;
        }
        x ^= basis[i];
    }
    return false;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector <int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector <pii> Q[n];
    for (int i = 0, l, x; i < q; ++i) {
        cin >> l >> x, l--;
        Q[l].eb(x, i);
    }
    vector <int> ans(q);
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += add(a[i]);
        for (pii A : Q[i]) {
            int x = A.X;
            for (int j = 19; ~j; --j) if (x & (1 << j)) {
                if (!basis[j]) break;
                else x ^= basis[j];
            }
            if (x) ans[A.Y] = -1;
            else ans[A.Y] = i + 1 - cnt;
        }
    }
    lli pw2[n + 1];
    pw2[0] = 1;
    for (int i = 0; i < n; ++i) pw2[i + 1] = pw2[i] * 2 % mod;
    for (int i : ans) cout << (~i ? pw2[i] : 0) << '\n';
}

CF - 1101G

連結

題意

有一個長度為nn的序列，問你最多可以將陣列切成幾段，使的沒有一個線段subset的xor值為0，若無解請輸出-1

(1≤n≤200000)(1 \leq n \leq 200000)

作法

若陣列xor起來為0，則答案是-1
否則這題的答案就是∣B∣|B|

原因的話假設我們算好preipre_i代表陣列前ii項的xor值
那麼我們切成kk段，切在i1,i2,...,ik=ni_1, i_2, ..., i_k = n
則所形成的線段為pre0⊕prei1,prei1⊕prei2,...,preik−1⊕prenpre_0 \oplus pre_{i_1}, pre_{i_1} \oplus pre_{i_2}, ..., pre_{i_{k - 1}} \oplus pre_n
要使這東東沒有subset的xor為0代表k≤∣B∣k \leq |B|
所以答案就會是線性基維度~

code就不附了，長的跟前面差不多

CF - 1100F

連結

題意

有一個長度為nn的序列，有qq筆詢問，每筆給你l,rl, r問區間[l,r][l, r]組成的subset的xor最大值

(1≤n,q≤500000)(1 \leq n, q \leq 500000)

作法

看官解才會，我就爛= =
我們將詢問按照rr排好，這樣問題會變成要如何在插入basis的時候多紀錄一些東西，使每次可以給定ll直接詢問答案

因此，我們在加入的時候多紀錄加入的時間，然後在加入basis的時候，若當前的basis時間較小，就可以將他替換掉，然後再繼續跑下去
寫成扣大概會長這樣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int basis[20], T[20];

void add(int x, int t) {
    for (int i = 19; ~i; --i) if (x >> i & 1) {
        if (basis[i]) {
            if (T[i] < t) {
                swap(basis[i], x);
                swap(T[i], t);
            }
        } else {
            basis[i] = x;
            T[i] = t;
            return;
        }
        x ^= basis[i];
    }
}

之後詢問就相當單純，一樣採取greedy的策略，挑選加入時間≥l\geq l的basis即可

時間複雜度是好好的O((n+q)logC)\mathcal{O}((n + q)logC)

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
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
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 400008, logN = 17, K = 333;

int basis[20], T[20];

void add(int x, int t) {
    for (int i = 19; ~i; --i) if (x >> i & 1) {
        if (basis[i]) {
            if (T[i] < t) {
                swap(basis[i], x);
                swap(T[i], t);
            }
        } else {
            basis[i] = x;
            T[i] = t;
            return;
        }
        x ^= basis[i];
    }
}

int query(int t) {
    int ans = 0;
    for (int i = 19; ~i; --i) if (!(ans >> i & 1) && basis[i] && t <= T[i]) {
        ans ^= basis[i];
    }
    return ans;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n;
    vector <int> a(n);
    vector <pii> Q[n];
    for (int i = 0; i < n; ++i) cin >> a[i];
    cin >> q;
    vector <int> ans(q);
    for (int i = 0, l, r; i < q; ++i) {
        cin >> l >> r, l--, r--;
        Q[r].eb(l, i);
    }
    for (int i = 0; i < n; ++i) {
        add(a[i], i);
        for (pii &A : Q[i]) {
            ans[A.Y] = query(A.X);
        }
    }
    for (int &i : ans) cout << i << '\n';
}