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 (tính cả tập rỗng). Mỗi giá trị đạt được bởi đúng $2^{n - r}$ tập con của $n$ số ban đầu.

Trong hình, bit bật mà đã có trục thì XOR với trục đó; gặp bit trống thì số đang xét thành trục mới.

XOR lớn nhất

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. 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 $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ở, 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.

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 vài phần tử trước, không làm không gian lớn thêm.

Bước 2: tham lam.

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;
#define 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';
}

ChạyInput4
1 2 7 8

Output15

$O(31n)$. Vòng chèn duyệt đủ mọi bit dù đa số bit của $x$ đã tắt. Nhảy thẳng tới bit cao nhất còn bật sẽ bớt được nhiều bước:

Dùng __builtin_clzll để nhảy tới bit cao nhất nhanh hơn duyệt đủ 60 bit khoảng 2 lần. Quy tắc: vòng lặp theo bit mà phần lớn bước không làm gì thì thay bằng lệnh nhảy tới bit cần.

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;
#define 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';
}

ChạyInput3 2 4
1 2 4

Output1 2 3

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

Tập độc lập

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ữ 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à đổ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;
#define 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';
}

ChạyInput3
1 5
2 4
3 10

Output15

Độ phức tạp: $O(N \log N + 60N)$.

Cơ sở trên đoạn

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 q : at[r]) {
        int l = q.first, id = q.second, 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;
#define 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 q : at[r]) {
            int l = q.first, id = q.second, 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';
}

ChạyInput4
1 2 4 8
3
1 3
2 4
3 3

Output7
14
4

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

Chu trình đồ 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 e : adj[u]) {
    int v = e.first;
    ll w = e.second;
    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;
#define 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 e : adj[u]) {
            int v = e.first;
            ll w = e.second;
            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';
}

ChạyInput3 3
1 2 1
2 3 2
1 3 7

Output7

Độ phức tạp: $O(N + 60M)$.