XOR Basis

Chèn vào cơ sở

Giữ mảng b[i]: hoặc 0, hoặc một số có bit cao nhất đúng là $i$ (vector trục của bit $i$). Chèn $x$: duyệt bit từ cao xuống; gặp bit $i$ bật trong $x$ thì nếu b[i] trống, đặt b[i] = x và dừng; nếu không, $x \leftarrow x \oplus b[i]$ để tắt bit $i$. Nếu $x$ về 0 thì nó đã biểu diễn được bằng các số trước, tức phụ thuộc.

Phép $x \oplus b[i]$ không đổi không gian sinh, chỉ đổi cách viết. Số vector trục khác 0 là hạng $r$. Mỗi giá trị trong không gian sinh có đúng một cách viết bằng các vector trục, nên có đúng $2^r$ giá trị XOR phân biệt; mỗi giá trị đạt được bởi đúng $2^{n - r}$ tập con của $n$ số ban đầu.

Ví dụSố giá trị XOR phân biệt

Đề. $n \le 2 \cdot 10^5$ số tới $10^9$. Đếm số giá trị XOR phân biệt của các tập con, tính cả tập rỗng.

Lời giải. Chèn mọi số vào cơ sở XOR, đếm số lần chèn thành công, tức hạng $r$. Các giá trị XOR của tập con chính là không gian sinh bởi cơ sở. Mỗi tập con của $r$ trục cho một giá trị khác nhau, vì trục cao nhất khác nhau quyết định bit cao nhất khác nhau. Vậy có đúng $2^r$ giá trị, tính cả 0 của tập rỗng.

Bước 1: chèn vào cơ sở. Duyệt bit từ cao xuống; bit $i$ của $x$ bật mà đã có trục b[i] thì XOR để tắt bit đó. Gặp bit bật mà chưa có trục thì $x$ (đã khử) thành trục mới. Đi hết mà không tạo trục thì $x$ đã về 0: nó là XOR của một số phần tử trước, không làm không gian lớn thêm.

void insert(ll x) {
    for (ll i = 30; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!b[i]) {
            b[i] = x;
            rk++;
            return;
        }
        x ^= b[i];
    }
}

In 1LL << rk vì hạng tới 30.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, b[31], rk;

void insert(ll x) {
    for (ll i = 30; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!b[i]) {
            b[i] = x;
            rk++;
            return;
        }
        x ^= b[i];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        insert(x);
    }
    cout << (1LL << rk) << '\n';
}

Input3
1 2 3

Output4

Mỗi lần chèn 31 bước.

XOR lớn nhất và cơ sở rút gọn

XOR lớn nhất. Bắt đầu từ $res = 0$, duyệt bit từ cao xuống: nếu $res \oplus b[i] > res$ thì lấy. Vector trục $b[i]$ chỉ ảnh hưởng bit $i$ và các bit thấp hơn, nên quyết định ở bit $i$ không bao giờ bị các bước sau làm hỏng. Bắt đầu từ một giá trị $x$ thay vì 0 thì được $\max (x \oplus s)$ trên không gian sinh.

Cơ sở rút gọn. Khử thêm: với mỗi trục $i$, xóa bit $i$ khỏi mọi trục cao hơn có bit đó. Khi ấy bit trục $i$ chỉ xuất hiện trong $b[i]$. Xếp các trục theo bit tăng dần $c_0 < c_1 < \dots < c_{r-1}$; giá trị nhỏ thứ $t$ (đếm từ 0, giá trị 0 là thứ 0) là XOR các $c_j$ mà bit $j$ của $t$ bật, vì so hai tổ hợp chỉ cần so trục cao nhất khác nhau.

Ví dụXOR tập con lớn nhất

Đề. $n \le 2 \cdot 10^5$ số tới $10^9$. Tìm XOR lớn nhất của một tập con.

Lời giải. Chèn mọi số vào cơ sở như ví dụ trước, rồi dựng đáp án từ bit cao xuống: với mỗi trục $b[i]$, lấy nó nếu làm kết quả lớn hơn. Trục $b[i]$ có bit cao nhất là $i$, nên chỉ đổi bit $i$ và các bit thấp hơn; quyết định ở bit $i$ vì vậy không bị các bước sau làm hỏng.

ll res = 0;
for (ll i = 30; i >= 0; i--) res = max(res, res ^ b[i]);

Lấy trục khi bit $i$ của res đang tắt, bỏ qua khi đang bật; trục chưa có (b[i] = 0) không làm đổi gì.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, b[31];

void insert(ll x) {
    for (ll i = 30; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!b[i]) {
            b[i] = x;
            return;
        }
        x ^= b[i];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        insert(x);
    }
    ll res = 0;
    for (ll i = 30; i >= 0; i--) res = max(res, res ^ b[i]);
    cout << res << '\n';
}

Input4
1 2 7 8

Output15

$O(31n)$.

Ví dụMột đoạn trong thứ tự XOR

Đề. Dãy $N \le 2 \cdot 10^5$ số dưới $2^{60}$. Sắp các giá trị XOR phân biệt (gồm 0) tăng dần thành $s_1 < s_2 < \dots$; in $s_L, \dots, s_R$ với $R - L + 1 \le 2 \cdot 10^5$.

Lời giải. Rút gọn cơ sở để bit trục $i$ chỉ còn xuất hiện trong $b[i]$. Xếp các trục theo bit tăng dần $c_0 < c_1 < \dots < c_{r-1}$. So hai giá trị sinh từ cơ sở rút gọn chỉ cần xem trục cao nhất mà một bên dùng còn bên kia không, nên thứ tự các giá trị trùng với thứ tự nhị phân của tập trục được dùng. Giá trị nhỏ thứ $t$ (đếm từ 0) là XOR các $c_j$ mà bit $j$ của $t$ bật; $s_L$ ứng với $t = L - 1$.

Bước 1: rút gọn. Với trục $i$ từ thấp lên, mọi trục cao hơn có bit $i$ bật thì XOR với $b[i]$ để tắt nó. Trục $b[i]$ chỉ chứa các bit không cao hơn $i$, nên phép XOR không làm hỏng bit trục cao.

for (ll i = 0; i < 60; i++)
    if (b[i])
        for (ll j = i + 1; j < 60; j++)
            if (b[j] >> i & 1) b[j] ^= b[i];

Bước 2: giá trị thứ $t$. c là các trục khác 0 theo thứ tự bit tăng; bit $j$ của $t$ quyết định có dùng $c_j$ không.

for (ll t = L - 1; t <= R - 1; t++) {
    ll v = 0;
    for (ll j = 0; j < (ll)c.size(); j++)
        if (t >> j & 1) v ^= c[j];
    cout << v << ' ';
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, L, R, b[60];

void insert(ll x) {
    for (ll i = 59; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!b[i]) {
            b[i] = x;
            return;
        }
        x ^= b[i];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> L >> R;
    for (ll i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        insert(x);
    }
    for (ll i = 0; i < 60; i++)
        if (b[i])
            for (ll j = i + 1; j < 60; j++)
                if (b[j] >> i & 1) b[j] ^= b[i];
    vector<ll> c;
    for (ll i = 0; i < 60; i++)
        if (b[i]) c.push_back(b[i]);
    for (ll t = L - 1; t <= R - 1; t++) {
        ll v = 0;
        for (ll j = 0; j < (ll)c.size(); j++)
            if (t >> j & 1) v ^= c[j];
        cout << v << ' ';
    }
    cout << '\n';
}

Input3 2 4
1 2 4

Output1 2 3

$60(R - L + 1)$ bước để in.

Tập độc lập có trọng số lớn nhất

Chọn tập con độc lập (không tập con khác rỗng nào có XOR bằng 0) có tổng trọng số lớn nhất: sắp theo trọng số giảm dần, chèn lần lượt, giữ lại phần tử nào chèn thành công. Tham lam đúng vì các tập độc lập tạo thành một matroid: mọi tập độc lập cực đại có cùng kích thước (bằng hạng), và có thể đổi phần tử để tăng trọng số như trong thuật toán Kruskal. Cũng cách này cho bài “mua ít tiền nhất để đủ hạng”: sắp theo giá tăng dần.

Ví dụTập mã có trọng số

Đề. $N \le 1000$ loại quặng, mỗi loại có mã tới $10^{18}$ và sức mạnh tới $10^4$. Chọn các loại sao cho không tập con khác rỗng nào có XOR mã bằng 0, tổng sức mạnh lớn nhất.

Lời giải. Tập mã không có tập con XOR bằng 0 chính là tập độc lập tuyến tính. Các tập độc lập tạo thành matroid, nên tham lam như Kruskal là đúng: xét các loại theo sức mạnh giảm dần, giữ loại nào chèn vào cơ sở thành công. Chèn thất bại nghĩa là mã đó là XOR của một số mã đã chọn, tức thêm nó sẽ tạo tập con XOR bằng 0.

Bước 1: chèn có báo kết quả. insert trả về có tạo trục mới hay không. Mã tới $10^{18} < 2^{60}$ nên cơ sở 60 bit là đủ.

Bước 2: tham lam. a[i] lưu cặp (sức mạnh, mã) để sort sắp theo sức mạnh; duyệt từ cuối mảng là sức mạnh giảm dần.

sort(a + 1, a + n + 1);
for (ll i = n; i >= 1; i--)
    if (insert(a[i].second)) sum += a[i].first;

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, b[60];
pair<ll, ll> a[1005];

bool insert(ll x) {
    for (ll i = 59; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!b[i]) {
            b[i] = x;
            return 1;
        }
        x ^= b[i];
    }
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i].second >> a[i].first;
    sort(a + 1, a + n + 1);
    ll sum = 0;
    for (ll i = n; i >= 1; i--)
        if (insert(a[i].second)) sum += a[i].first;
    cout << sum << '\n';
}

Input3
1 5
2 4
3 10

Output15

$O(N \log N + 60N)$.

Cơ sở theo tiền tố, giữ vị trí mới nhất

Hỏi XOR lớn nhất của tập con trong đoạn $[l, r]$. Quét $r$ tăng dần và giữ một cơ sở của tiền tố $1..r$, nhưng mỗi trục ghi kèm vị trí $pos$, và ưu tiên trục có vị trí lớn nhất: khi chèn $x$ (vị trí $p$) gặp trục $b[i]$ cũ hơn ($pos_i < p$), đổi chỗ $x$ với $b[i]$ cùng vị trí, rồi tiếp tục khử với phần tử cũ. Khi đó các trục có $pos \ge l$ sinh ra đúng không gian của đoạn $[l, r]$, nên truy vấn chỉ tham lam trên các trục đó.

Làm ngoại tuyến (sắp truy vấn theo $r$) tốn $O((n + q) \log V)$ thời gian và một cơ sở bộ nhớ; muốn trực tuyến thì lưu bản sao cơ sở của mọi tiền tố.

Ví dụXOR lớn nhất trên đoạn

Đề. Dãy $n \le 5 \cdot 10^5$ số tới $10^6$, $q \le 5 \cdot 10^5$ đoạn $[l, r]$: XOR lớn nhất của một tập con trong đoạn.

Lời giải. Làm ngoại tuyến: gom truy vấn theo đầu phải $r$. Quét $r$ tăng dần, giữ cơ sở của tiền tố $1..r$ mà mỗi trục nhớ vị trí pb, và luôn ưu tiên trục có vị trí lớn nhất. Khi đó các trục có $pb \ge l$ sinh ra đúng không gian của các phần tử trong $[l, r]$. Truy vấn $[l, r]$ là tham lam XOR lớn nhất trên các trục đó. Giá trị dưới $2^{20}$ nên cơ sở 20 bit.

Bước 1: chèn ưu tiên phần tử mới. Ở bit $i$ đã có trục mà trục đó cũ hơn ($pb_i < p$) thì đổi chỗ: phần tử mới chiếm trục, phần tử cũ tiếp tục đi xuống để khử. Không gian sinh không đổi, chỉ thay vector đứng đại diện.

void insert(int x, int p) {
    for (int i = 19; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!b[i]) {
            b[i] = x, pb[i] = p;
            return;
        }
        if (p > pb[i]) swap(b[i], x), swap(pb[i], p);
        x ^= b[i];
    }
}

Vì sao đúng: sau mỗi lần chèn, trục ở bit $i$ là phần tử mới nhất có thể đứng ở đó. Các trục có vị trí $\ge l$ được dựng hoàn toàn từ phần tử trong $[l, r]$, và mọi phần tử của $[l, r]$ đều biểu diễn được qua chúng, vì phần bị đẩy xuống trong lúc chèn luôn cũ hơn chính phần tử đẩy nó.

Bước 2: trả lời theo đầu phải. Tham lam từ bit cao như ví dụ XOR lớn nhất, bỏ qua trục có pb[i] < l.

for (int r = 1; r <= n; r++) {
    insert(c[r], r);
    for (auto [l, id] : at[r]) {
        int res = 0;
        for (int i = 19; i >= 0; i--)
            if (pb[i] >= l && (res ^ b[i]) > res) res ^= b[i];
        ans[id] = res;
    }
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 5e5 + 5;
int n, q, c[N], ans[N], b[20], pb[20];
vector<pair<int, int>> at[N];

void insert(int x, int p) {
    for (int i = 19; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!b[i]) {
            b[i] = x, pb[i] = p;
            return;
        }
        if (p > pb[i]) swap(b[i], x), swap(pb[i], p);
        x ^= b[i];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        at[r].push_back({l, i});
    }
    for (int r = 1; r <= n; r++) {
        insert(c[r], r);
        for (auto [l, id] : at[r]) {
            int res = 0;
            for (int i = 19; i >= 0; i--)
                if (pb[i] >= l && (res ^ b[i]) > res) res ^= b[i];
            ans[id] = res;
        }
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

Input4
1 2 4 8
3
1 3
2 4
3 3

Output7
14
4

$O((n + q) \cdot 20)$, chỉ một cơ sở trong bộ nhớ.

Chu trình trong đồ thị

XOR của một walk (được lặp đỉnh, cạnh) từ $1$ tới $n$: đi một cạnh hai lần thì nó triệt tiêu. Vì vậy mọi walk có giá trị bằng XOR của một đường đi cố định cộng với XOR của một số chu trình: đi ra chu trình, vòng một lần, đi về bằng đúng đường cũ. Các chu trình sinh ra một không gian, và chỉ cần các chu trình cơ bản: dựng cây BFS với $d_v$ là XOR từ gốc tới $v$, mỗi cạnh ngoài cây $(u, v, w)$ cho chu trình $d_u \oplus d_v \oplus w$.

Đáp án lớn nhất là tham lam $\max(d_n \oplus s)$ trên cơ sở của các chu trình; nhỏ nhất thì tham lam ngược lại.

Ví dụHành Trình XOR Lớn Nhất

Đề. Đồ thị liên thông $N \le 5 \cdot 10^4$ đỉnh, $M \le 10^5$ cạnh trọng số tới $10^{18}$ (có thể có khuyên, cạnh song song). Tìm XOR lớn nhất của một walk từ 1 tới $N$.

Lời giải. Dựng cây BFS từ đỉnh 1, $d_v$ là XOR các cạnh trên đường cây từ 1 tới $v$. Mọi walk từ 1 tới $N$ có giá trị bằng $d_N$ XOR một tổ hợp các chu trình, và các chu trình cơ bản $d_u \oplus d_v \oplus w$ (một cho mỗi cạnh ngoài cây) sinh ra mọi chu trình. Chèn chúng vào cơ sở, rồi tham lam lấy XOR lớn nhất bắt đầu từ $d_N$ thay vì từ 0.

Bước 1: BFS và chu trình. Gặp đỉnh mới thì ghi $d_v$; gặp đỉnh đã thăm thì chèn $d_u \oplus d_v \oplus w$. Cạnh cây gặp lại từ phía con cho đúng 0, và chèn 0 không làm gì. Cạnh ngoài cây được chèn hai lần (từ hai đầu) cùng một giá trị, lần sau cũng không làm gì. Khuyên cho chu trình $w$, cạnh song song cho XOR hai trọng số: tự được xử lý.

for (auto [v, w] : adj[u]) {
    if (!vis[v]) vis[v] = 1, d[v] = d[u] ^ w, q.push(v);
    else insert(d[u] ^ d[v] ^ w);
}

Bước 2: tham lam từ $d_N$. Kết quả là $\max(d_N \oplus s)$ trên mọi $s$ của không gian chu trình.

ll res = d[n];
for (int i = 59; i >= 0; i--) res = max(res, res ^ b[i]);

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 5e4 + 5;
int n, m;
ll d[N], b[60];
bool vis[N];
vector<pair<int, ll>> adj[N];

void insert(ll x) {
    for (int i = 59; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!b[i]) {
            b[i] = x;
            return;
        }
        x ^= b[i];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto [v, w] : adj[u]) {
            if (!vis[v]) vis[v] = 1, d[v] = d[u] ^ w, q.push(v);
            else insert(d[u] ^ d[v] ^ w);
        }
    }
    ll res = d[n];
    for (int i = 59; i >= 0; i--) res = max(res, res ^ b[i]);
    cout << res << '\n';
}

Input3 3
1 2 1
2 3 2
1 3 7

Output7

$O(N + 60M)$.