Hướng dẫn cho LQDOJ CUP 2022 - Round 3 - XORSEG

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: ngpin_04

Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 20\).

Tutorial

Với mỗi truy vấn ta sinh nhị phân để duyệt tất cả các cách lập đội trên đoạn \([l, r]\).

Độ phức tạp: \(\mathcal{O}(2^n \cdot q)\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;

int n, numQuery;
int a[MAX_N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("XORSEG.inp", "r", stdin);
    freopen("XORSEG.out", "w", stdout);

    cin >> n >> numQuery;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    while (numQuery--) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, x;
            cin >> pos >> x;
            a[pos] = x;
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            int answer = 0;
            for (int mask = 1; mask < (1LL << (r - l + 1)); mask++) {
                int cur = 0;
                for (int i = l; i <= r; i++) {
                    if ((mask >> (i - l)) & 1) {
                        cur ^= a[i];
                    }
                }
                answer += (cur == x);
            }
            cout << answer << "\n";
        }
    }

    return 0;
}

Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10 ^ 3\), \(a_i \leq 10 ^ 3\), không có yêu cầu loại \(1\) và mọi yêu cầu loại 2 đều có \(l = 1\).

Tutorial

Vì không có truy vấn thay đổi, giá trị \(a[i]\) nhỏ và mọi truy vấn đoạn đều có \(l = 1\) nên ta có thể sử dụng hàm quy hoạch động \(dp(i, xorsum)\) là số cách chọn đội nếu xét những người từ \(1\) đến \(i\) và tổng xor của các người đó là \(xorsum\).

Độ phức tạp: \(\mathcal{O}(n^2)\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2005;
const int MOD = 1e9 + 7;

int n, numQuery;
int a[MAX_N], dp[MAX_N][MAX_N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("XORSEG.inp", "r", stdin);
    freopen("XORSEG.out", "w", stdout);

    cin >> n >> numQuery;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (1 << 10); j++) {
            dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
            dp[i][j] = (dp[i][j] + dp[i - 1][j ^ a[i]]) % MOD;
        }
    }

    while (numQuery--) {
        int type, l, r, x;
        cin >> type >> l >> r >> x;
        cout << dp[r][x] << "\n";
    }

    return 0;
}

Sơ lược về xor basis

Ta xem biểu diễn các số tự nhiên dưới dạng nhị phân là một vector,

\(28_{10} = 011100_2\) \(\rightarrow\) \([0, 1, 1, 1, 0, 0]\)

Ở trong đại số tuyến tính thông thường ta có một tập basis vector có thể biểu diễn tất cả các vector khác trong không gian bằng tổ hợp tuyến tính của chúng, tuy nhiên ở trong xor basis, đặc biệt là ở hệ nhị phân thì tổ hợp của chúng chỉ bao gồm \(0/1\).

Số lượng chiều của vector tối đa là \(\log(a[i])\) nên số lượng vector tối đa trong basis cũng là \(\log(a[i])\).

Một tập vector sẽ được phân thành 2 phần (phần nằm trong basis và có thể biểu diễn bằng các vector trong basis).

Để gộp 2 tập vector lại với nhau thì ta chỉ cần gộp các vector của 2 basis lại với nhau (vì các vector không nằm trong basis không quan trọng).

Các bạn có thể đọc thêm về xor basis để hiểu rõ hơn.

Subtask \(3\) (\(30\%\) số điểm): \(n, q \leq 10 ^ 3\).

Tutorial

Duyệt từ \(l\) đến \(r\) và thêm các vector để xây dựng basis.

Khi truy vấn chỉ cần xét xem \(x\) có thể được tạo bởi tổ hợp các vector basis hay không, nếu được thì đáp án sẽ là \(2^{cnt}\) với \(cnt\) là số lượng vector không nằm trong basis. Ngược lại đáp án là \(0\).

Độ phức tạp: \(\mathcal{O}(n \times q \times \log_2(a[i]))\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MOD = 1e9 + 7;
const int LOG = 20;

int n, numQuery;
int a[MAX_N];
int pw[MAX_N];
int res[LOG];

int getBit(int num, int pos) {
    return (num >> pos) & 1;
}

void add(int x, int base[], int &cnt) {
    for (int i = 0; i < LOG; i++) {
        if (getBit(x, i)) {
            if (base[i] == 0) {
                base[i] = x;
                return;
            }
            x ^= base[i];
        }
    }
    cnt++;
}

bool check(int x, int base[]) {
    for (int i = 0; i < LOG; i++) {
        if (getBit(x, i)) {
            if (base[i] == 0) {
                return false;
            }
            x ^= base[i];
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("XORSEG.inp", "r", stdin);
    freopen("XORSEG.out", "w", stdout);

    cin >> n >> numQuery;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i] = (pw[i - 1] << 1) % MOD;
    }

    while (numQuery--) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, x;
            cin >> pos >> x;
            a[pos] = x;
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            int cnt = 0;
            for (int i = 0; i < LOG; i++) {
                res[i] = 0;
            }
            for (int i = l; i <= r; i++) {
                add(a[i], res, cnt);
            }
            cout << check(x, res) * pw[cnt] << "\n";
        }
    }

    return 0;
}

Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Tutorial

Như trên, ta xây dựng một cây segment tree với mỗi nút của segment tree lưu trữ xor basis của đoạn mà nút đó quản lí.

Kết hợp giữa 2 xor basis độ phức tạp sẽ là \(\mathcal{O}(\log_2(a[i])^2)\).

Độ phức tạp: \(\mathcal{O}((n + q)\log(n)^3)\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MOD = 1e9 + 7;
const int LOG = 20;

int n, numQuery;
int pw[MAX_N];
int res[LOG];

int getBit(int num, int pos) {
    return (num >> pos) & 1;
}

struct SegmentTree {
private:
    int st[MAX_N * 4][LOG], cnt[MAX_N * 4];
    void add(int x, int base[], int &cnt) {
        for (int i = 0; i < LOG; i++) {
            if (getBit(x, i)) {
                if (base[i] == 0) {
                    base[i] = x;
                    return;
                }
                x ^= base[i];
            }
        }
        cnt++;
    }
    void combine(int base[], int cur[], int &num, int &cnt) {
        num += cnt;
        for (int i = 0; i < LOG; i++) {
            if (cur[i] > 0) {
                add(cur[i], base, num);
            }
        }
    }

    void update(int id, int low, int high, int pos, int x) {
        if (low > pos || high < pos) {
            return;
        }
        if (low == high) {
            for (int i = 0; i < LOG; i++) {
                st[id][i] = 0;
            }
            cnt[id] = 0;
            add(x, st[id], cnt[id]);
            return;
        }
        int mid = (low + high) >> 1;
        update(id << 1, low, mid, pos, x);
        update(id << 1 | 1, mid + 1, high, pos, x);
        for (int i = 0; i < LOG; i++) {
            st[id][i] = st[id << 1][i];
        }
        cnt[id] = cnt[id << 1];
        combine(st[id], st[id << 1 | 1], cnt[id], cnt[id << 1 | 1]);
    }

    void get(int id, int low, int high, int left, int right, int base[], int &num) {
        if (low > right || high < left) {
            return;
        }
        if (low >= left && high <= right) {
            combine(base, st[id], num, cnt[id]);
            return;
        }
        int mid = (low + high) >> 1;
        get(id << 1, low, mid, left, right, base, num);
        get(id << 1 | 1, mid + 1, high, left, right, base, num);
    }

public:
    void update(int pos, int x) {
        update(1, 1, n, pos, x);
    }

    void get(int left, int right, int base[], int &num) {
        get(1, 1, n, left, right, base, num);
    }
} segmentTree;

bool check(int x, int base[]) {
    for (int i = 0; i < LOG; i++) {
        if (getBit(x, i)) {
            if (base[i] == 0) {
                return false;
            }
            x ^= base[i];
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("XORSEG.inp", "r", stdin);
    freopen("XORSEG.out", "w", stdout);

    cin >> n >> numQuery;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        segmentTree.update(i, x);
    }

    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i] = (pw[i - 1] << 1) % MOD;
    }

    while (numQuery--) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, x;
            cin >> pos >> x;
            segmentTree.update(pos, x);
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            int cnt = 0;
            for (int i = 0; i < 20; i++) {
                res[i] = 0;
            }
            segmentTree.get(l, r, res, cnt);
            cout << check(x, res) * pw[cnt] << "\n";
        }
    }

    return 0;
}

Bình luận

Tải bình luận...

Không có bình luận nào.