跳转至

线性基

模版
C++
 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
template<class T, const int M = 30>
struct LinearBasis {
    vector<T> f;
    int cnt = 0;
    LinearBasis() {
        init();
    }
    void init() {
        f.assign(M + 1, 0);
    }
    bool insert(T x) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (f[i] == 0) {
                    f[i] = x;
                    cnt++;
                    return true;
                }
                x ^= f[i];
            }
        }
        return false;
    }
    T query(T x = 0) {
        for (int i = M ; i >= 0 ; i--) {
            if (!(x & T(1) << i)) {
                x ^= f[i];
            }
        }
        return x;
    }
    bool check(T x) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (f[i] != 0) {
                    x ^= f[i];
                } else {
                    return false;
                }
            }
        }
        return true;
    }
    friend LinearBasis operator+(LinearBasis x, LinearBasis y) {
        for (int i = M ; i >= 0 ; i--) {
            if (y.f[i] == 0) continue;
            x.insert(y.f[i]);
        }
        return x;
    }
}; // LinearBasis
C++
 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
template<class T, const int M = 30>
struct LinearBasis {
    vector<T> f, idx;
    int cnt = 0;
    LinearBasis() {
        init();
    }
    void init() {
        f.assign(M + 1, 0);
        idx.assign(M + 1, -1);
    }
    bool insert(T x, int id) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (idx[i] == -1) {
                    idx[i] = id;
                    f[i] = x;
                    cnt++;
                    return true;
                }
                x ^= f[i];
            }
        }
        return false;
    }
}; // LinearBasis
C++
 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
template<class T>
struct LinearBasis {
    vector<vector<T>> f;
    vector<int> idx;
    const T eps = 1e-5;
    int cnt = 0;
    int n, m;
    LinearBasis(int n, int m) : n(n), m(m) {
        init();
    }
    void init() {
        f.resize(0);
        idx.assign(m + 1, -1);
    }
    bool insert(vector<T> x, int id) {
        for (int i = 0 ; i < m ; i++) {
            if (fabs(x[i]) < eps) continue;
            if (idx[i] == -1) {
                idx[i] = cnt;
                f.push_back(x);
                cnt++;
                return true;
            }
            T z = x[i] / f[idx[i]][i];
            for (int j = i ; j < m ; j++) {
                x[j] -= z * f[idx[i]][j];
            }
        }
        return false;
    }
}; // LinearBasis
例题

P3812 【模板】线性基 - 洛谷

P4570 [BJWC2011] 元素 - 洛谷

P3265 [JLOI2015] 装备购买 - 洛谷

习题

P4301 [CQOI2013] 新Nim游戏 - 洛谷

在第一个回合中，双方可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。从第二个回合（又轮到第一个游戏者）开始，规则和 Nim 游戏一样。如果你先拿，怎样才能保证获胜？如果可以获胜的话，还要让第一回合拿的火柴总数尽量小。

只要开局异或和不为0就先手必胜，所以利用线性基，如果不能插入，则说明异或和可以为0，所以我们就要把不能插入的都拿走，对火柴进行降序排序，依次插入线性基，对不能插入的求和输出即可。

#114. k 大异或和 - LibreOJ

将所有元素插入线性基内，然后处理所有只有第i位为1的，将rank二进制分解即可。

代码
C++
 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;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
template<class T, const int M = 30> struct LinearBasis {
    int tot;
    vector<T> f, d;
    bool flag;
    LinearBasis() {
        init();
    }
    void init() {
        f.assign(M + 1, 0);
        d.assign(M + 1, 0);
        tot = 0;
        flag = false;
    }
    bool insert(T x) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (f[i] == 0) {
                    f[i] = x;
                    return true;
                }
                x ^= f[i];
            }
        }
        flag = true;
        return false;
    }
    void build() {
        for (int i = 0 ; i <= M ; i++) {
            for (int j = i + 1 ; j <= M ; j++) {
                if (f[j] & T(1) << i) {
                    f[j] ^= f[i];
                }
            }
            if (f[i]) {
                d[tot++] = f[i];
            }
        }
    }
    T query(long long rank) {
        if (flag) {
            rank--;
        }
        if (rank == 0) return 0;
        if (rank >= T(1) << tot) return -1;
        T ans = 0;
        for (int i = M ; i >= 0 ; i--) {
            if (rank & T(1) << i) {
                ans ^= d[i];
            }
        }
        return ans;
    }
}; // LinearBasis
int main() {
    LinearBasis<long long, 50> lb;
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        long long x;
        cin >> x;
        lb.insert(x);
    }
    lb.build();
    int q;
    cin >> q;
    while (q--) {
        long long x;
        cin >> x;
        cout << lb.query(x) << "\n";
    }
    return 0;
}

Problem - F - Codeforces

q次查询区间最大异或和，无修改。

可以建立n个前缀线性基，对于每个二进制位，维护标号最大

区间 \([L,R]\) 的答案为第 \(R\) 个线性基，对于标号都大于等于 \(L\) 的查询结果。

代码
C++
 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
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
template<class T, const int M = 30>
struct LinearBasis {
    vector<T> f, idx;
    int cnt = 0;
    LinearBasis() {
        init();
    }
    void init() {
        f.assign(M + 1, 0);
        idx.assign(M + 1, -1);
    }
    bool insert(T x, int id) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (idx[i] == -1) {
                    idx[i] = id;
                    f[i] = x;
                    cnt++;
                    return true;
                } else if (id > idx[i]) {
                    swap(id, idx[i]);
                    swap(f[i], x);
                }
                x ^= f[i];
            }
        }
        return false;
    }
    T query(int L) {
        T ans = 0;
        for (int i = M ; i >= 0 ; i--) {
            if (!(ans & T(1) << i) && idx[i] >= L) {
                ans ^= f[i];
            }
        }
        return ans;
    }
}; // LinearBasis
LinearBasis<int, 20> lb[500005];
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        int x;
        cin >> x;
        lb[i] = lb[i - 1];
        lb[i].insert(x, i);
    }
    int q;
    cin >> q;
    while (q--) {
        int L, R;
        cin >> L >> R;
        cout << lb[R].query(L) << "\n";
    }
    return 0;
}

P4839 P 哥的桶 - 洛谷

\(m\) 个桶，\(q\) 次操作。

操作 \(1\) 往某桶中放入一个数。

操作 \(2\) 这些桶中的数的最大异或和。

利用线段树维护 \(m\) 个线性基即可。

代码
C++
  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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
template<class T, const int M = 30>
struct LinearBasis {
    vector<T> f;
    int cnt = 0;
    LinearBasis() {
        init();
    }
    void init() {
        f.assign(M + 1, 0);
    }
    bool insert(T x) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (f[i] == 0) {
                    f[i] = x;
                    cnt++;
                    return true;
                }
                x ^= f[i];
            }
        }
        return false;
    }
    T query(T x = 0) {
        for (int i = M ; i >= 0 ; i--) {
            if (!(x & T(1) << i)) {
                x ^= f[i];
            }
        }
        return x;
    }
    bool check(T x) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (f[i] != 0) {
                    x ^= f[i];
                } else {
                    return false;
                }
            }
        }
        return true;
    }
    friend LinearBasis operator+(LinearBasis x, LinearBasis y) {
        for (int i = M ; i >= 0 ; i--) {
            if (y.f[i] == 0) continue;
            x.insert(y.f[i]);
        }
        return x;
    }
}; // LinearBasis
struct Info {
    int L, R;
    LinearBasis<int, 30> lb;
} tr[50005 << 2];
Info pushup(Info lhs, Info rhs) {
    Info res;
    res.L = lhs.L;
    res.R = rhs.R;
    res.lb = lhs.lb + rhs.lb;
    return res;
}
long long a[50005];
void build(int L, int R, int p = 1) {
    if (L == R) {
        tr[p].L = L;
        tr[p].R = R;
        return;
    }
    int mid = L + R >> 1;
    build(L, mid, p << 1);
    build(mid + 1, R, p << 1 | 1);
    tr[p] = pushup(tr[p << 1], tr[p << 1 | 1]);
}
void modify(int QL, int QR, int p = 1) {
    if (QL <= tr[p].L && tr[p].R <= QR) {
        tr[p].lb.insert(a[tr[p].L]);
        return;
    }
    int mid = tr[p].L + tr[p].R >> 1;
    if (QL <= mid) modify(QL, QR, p << 1);
    if (QR >= mid + 1) modify(QL, QR, p << 1 | 1);
    tr[p] = pushup(tr[p << 1], tr[p << 1 | 1]);
}
 LinearBasis<int, 30> query(int QL, int QR, int p = 1) {
    if (QL <= tr[p].L && tr[p].R <= QR) {
        return tr[p].lb;
    }
    int mid = tr[p].L + tr[p].R >> 1;
    if (QR <= mid) return query(QL, QR, p << 1);
    else if (QL >= mid + 1) return query(QL, QR, p << 1 | 1);
    return query(QL, QR, p << 1) + query(QL, QR, p << 1 | 1);
}
int main() {
    int n, m;
    cin >> n >> m;
    build(1, n);
    for (int i = 1 ; i <= n ; i++) {
        int op, L, R;
        cin >> op >> L >> R;
        if (op == 1) {
            a[L] = R;
            modify(L, L);
        } else {
            auto res = query(L, R);
            cout << res.query() << "\n";
        }
    }
    return 0;
}

P5607 [Ynoi2013] 无力回天 NOI2017 - 洛谷

操作一，区间异或 操作二，区间查询，异或上v的最大值

令 \(b[i]=a[i]\oplus a[i-1]\)，则\(a[L]\) 到 \(a[R]\) 之间的线性基等价于 \(b[L+1]\) 到 \(b[R]\) 的线性基再加上一个 \(a[L]\)

修改的话，因为 \(b\) 是差分数组，所以只需要 \(b[L]\oplus =v\) 和 \(b[R+1]\oplus =v\) 即可。

查询，利用线段树求 \(b[L,R]\) 的线性基，再插入 \(a[L]\) 即可。

代码
C++
  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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
template<class T, const int M = 30>
struct LinearBasis {
    vector<T> f;
    int cnt = 0;
    LinearBasis() {
        init();
    }
    void init() {
        f.assign(M + 1, 0);
    }
    bool insert(T x) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (f[i] == 0) {
                    f[i] = x;
                    cnt++;
                    return true;
                }
                x ^= f[i];
            }
        }
        return false;
    }
    T query(T x = 0) {
        for (int i = M ; i >= 0 ; i--) {
            if (!(x & T(1) << i)) {
                x ^= f[i];
            }
        }
        return x;
    }
    bool check(T x) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (f[i] != 0) {
                    x ^= f[i];
                } else {
                    return false;
                }
            }
        }
        return true;
    }
    friend LinearBasis operator+(LinearBasis x, LinearBasis y) {
        for (int i = M ; i >= 0 ; i--) {
            if (y.f[i] == 0) continue;
            x.insert(y.f[i]);
        }
        return x;
    }
}; // LinearBasis
struct Info {
    int L, R;
    LinearBasis<int, 30> lb;
} tr[50005 << 2];
Info pushup(Info lhs, Info rhs) {
    Info res;
    res.L = lhs.L;
    res.R = rhs.R;
    res.lb = lhs.lb + rhs.lb;
    return res;
}
int a[50005];
void build(int L, int R, int p = 1) {
    if (L == R) {
        tr[p].L = L;
        tr[p].R = R;
        tr[p].lb.insert(a[L]);
        return;
    }
    int mid = L + R >> 1;
    build(L, mid, p << 1);
    build(mid + 1, R, p << 1 | 1);
    tr[p] = pushup(tr[p << 1], tr[p << 1 | 1]);
}
void modify(int QL, int QR, int k, int p = 1) {
    if (QL <= tr[p].L && tr[p].R <= QR) {
        a[tr[p].L] ^= k;
        tr[p].lb.init();
        tr[p].lb.insert(a[tr[p].L]);
        return;
    }
    int mid = tr[p].L + tr[p].R >> 1;
    if (QL <= mid) modify(QL, QR, k, p << 1);
    if (QR >= mid + 1) modify(QL, QR, k, p << 1 | 1);
    tr[p] = pushup(tr[p << 1], tr[p << 1 | 1]);
}
LinearBasis<int, 30> query(int QL, int QR, int p = 1) {
    if (QL <= tr[p].L && tr[p].R <= QR) {
        return tr[p].lb;
    }
    int mid = tr[p].L + tr[p].R >> 1;
    if (QR <= mid) return query(QL, QR, p << 1);
    else if (QL >= mid + 1) return query(QL, QR, p << 1 | 1);
    return query(QL, QR, p << 1) + query(QL, QR, p << 1 | 1);
}
int lowbit(const int x) {
    return x & -x;
}
int n;
int sum[50005];
int query(int x) {
    int res = 0;
    while (x) {
        res ^= sum[x];
        x -= lowbit(x);
    }
    return res;
}
void add(int x, int k) {
    while (x <= 50000) {
        sum[x] ^= k;
        x += lowbit(x);
    }
}
int main() {
    int m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    for (int i = n ; i > 1 ; i--) {
        a[i] ^= a[i - 1];
    }
    for (int i = 1 ; i <= n ; i++) {
        add(i, a[i]);
    }
    build(1, n);
    for (int i = 1 ; i <= m ; i++) {
        int op, L, R, v;
        cin >> op >> L >> R >> v;
        if (op == 1) {
            add(L, v);
            modify(L, L, v);
            if (R + 1 <= n) {
                add(R + 1, v);
                modify(R + 1, R + 1, v);
            }
        } else {
            LinearBasis<int> lb;
            if (L != R) lb = query(L + 1, R);
            lb.insert(query(L));
            cout << lb.query(v) << "\n";
        }
    }
    return 0;
}

P3292 [SCOI2016] 幸运数字 - 洛谷

倍增，将路径所有点放进线性基求解

代码
C++
  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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
template<class T, const int M = 30>
struct LinearBasis {
    vector<T> f;
    int cnt = 0;
    LinearBasis() {
        init();
    }
    void init() {
        f.assign(M + 1, 0);
    }
    bool insert(T x) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (f[i] == 0) {
                    f[i] = x;
                    cnt++;
                    return true;
                }
                x ^= f[i];
            }
        }
        return false;
    }
    T query(T x = 0) {
        for (int i = M ; i >= 0 ; i--) {
            if (!(x & T(1) << i)) {
                x ^= f[i];
            }
        }
        return x;
    }
    bool check(T x) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (f[i] != 0) {
                    x ^= f[i];
                } else {
                    return false;
                }
            }
        }
        return true;
    }
    friend LinearBasis operator+(LinearBasis x, LinearBasis y) {
        for (int i = M ; i >= 0 ; i--) {
            if (y.f[i] == 0) continue;
            x.insert(y.f[i]);
        }
        return x;
    }
}; // LinearBasis
LinearBasis<long long, 60> f[20005][16];
vector<int> adj[20005];
int fa[20005][16], deep[20005];
long long val[20005];
void dfs(int u, int p) {
    deep[u] = deep[p] + 1;
    fa[u][0] = p;
    f[u][0].insert(val[u]);
    for (int i = 1 ; i <= 15 ; i++) {
        f[u][i] = f[u][i - 1] + f[fa[u][i - 1]][i - 1];
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (auto &to : adj[u]) {
        if (to == p) continue;
        dfs(to, u);
    }
}
int LCA(int x, int y) {
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = 15 ; i >= 0 ; i--) {
        if (deep[fa[x][i]] < deep[y]) continue;
        x = fa[x][i];
    }
    if (x == y) return x;
    for (int i = 15 ; i >= 0 ; i--) {
        if (fa[x][i] == fa[y][i]) continue;
        x = fa[x][i];
        y = fa[y][i];
    }
    return fa[x][0];
}
long long get(int x, int y) {
    int k = LCA(x, y);
    LinearBasis<long long, 60> res;
    res.insert(val[k]);
    for (int i = 15 ; i >= 0 ; i--) {
        if (deep[fa[x][i]] >= deep[k]) {
            res = res + f[x][i];
            x = fa[x][i];
        }
        if (deep[fa[y][i]] >= deep[k]) {
            res = res + f[y][i];
            y = fa[y][i];
        }
    }
    return res.query();
}
int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1 ; i <= n ; i++) {
        cin >> val[i];
    }
    for (int i = 1 ; i < n ; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << get(x, y) << "\n";
    }
    return 0;
}

P4151 [WC2011] 最大XOR和路径 - 洛谷

问从 \(1\) 走到 \(n\) 的路径权值的异或和最大值。

先是从 \(1\) 直接走到 \(n\)。此时权值异或和为 \(dist[n]\)。

在这个基础上增广，如果不走环，是不可能到终点的，所以我们选择环来增广。

如果我们走一个环，那么相当于我们选择走这个环的权值为 \(dist[to]\oplus dist[u]\oplus w\)。

插入线性基即可。

本方法也可以求最小XOR和路径。

代码
C++
 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
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
template<class T, const int M = 30>
struct LinearBasis {
    vector<T> f;
    int cnt = 0;
    LinearBasis() {
        init();
    }
    void init() {
        f.assign(M + 1, 0);
    }
    bool insert(T x) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (f[i] == 0) {
                    f[i] = x;
                    cnt++;
                    return true;
                }
                x ^= f[i];
            }
        }
        return false;
    }
    T query(T x = 0) {
        for (int i = M ; i >= 0 ; i--) {
            if (!(x & T(1) << i)) {
                x ^= f[i];
            }
        }
        return x;
    }
    bool check(T x) {
        for (int i = M ; i >= 0 ; i--) {
            if (x & T(1) << i) {
                if (f[i] != 0) {
                    x ^= f[i];
                } else {
                    return false;
                }
            }
        }
        return true;
    }
    friend LinearBasis operator+(LinearBasis x, LinearBasis y) {
        for (int i = M ; i >= 0 ; i--) {
            if (y.f[i] == 0) continue;
            x.insert(y.f[i]);
        }
        return x;
    }
}; // LinearBasis
LinearBasis<long long, 62> LB;
vector<pair<int, long long>> adj[50005];
bool vis[50005];
long long dist[50005];
void dfs(int u, int p) {
    vis[u] = true;
    for (auto &[to, w] : adj[u]) {
        if (to == p) continue;
        if (vis[to]) {
            LB.insert(dist[u] ^ w ^ dist[to]);
            continue;
        }
        dist[to] = dist[u] ^ w;
        dfs(to, u);
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0 ; i < m ; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    dfs(1, 0);
    cout << LB.query(dist[n]) << "\n";
    return 0;
}