Xor Vector
(math/matrix/xorvector.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "math/matrix/xorvector.hpp"

概要

掃き出せるvector<long long>.

計算量

• 掃き出し法 : $O(nb)$ ($b$はビットサイズ)

使用例

• XorVector vec(n) : 最大サイズ$n$のvectorを定義.
• vec.emplace(m) : $m$を追加.
• vec.find(m) : いくつかの要素のXORが$m$になるかを返す.
• vec.gaussian_elimination() : 掃き出し法.
• vec.print() : デバッグ出力.

問題例

• ABC141F - Xor Sum 3
• AGC045A - Xor Battle
• codeFlyer D - 数列 XOR

Verified with

• test/yukicoder/184.test.cpp

Code

/**
* @brief Xor Vector
* @docs docs/math/matrix/xorvector.md
*/

struct XorVector {
    bool dirty = false;
    int rank, N;
    vector<long long> span;
    XorVector(int N)
        : rank(0), N(N), span(N, 0) {}
    void emplace(ll num) {
        span[rank++] = num;
        dirty        = true;
    }
    bool find(ll num) {
        if (num == 0) return true;
        if (dirty) gaussian_elimination();
        for (int i = 0; i < rank; ++i) {
            if (span[i] == 0LL) break;
            num = min(num, num ^ span[i]);
        }
        return num == 0LL;
    }
    void gaussian_elimination() {
        rank = 0;
        for (int col = 63; col >= 0; --col) {
            int pivot = -1;
            for (int row = rank; row < N; ++row)
                if (span[row] >> col & 1) {
                    pivot = row;
                    break;
                }
            if (pivot == -1) continue;
            swap(span[pivot], span[rank]);
            for (int row = 0; row < N; ++row)
                if (row != rank and span[row] >> col & 1) span[row] ^= span[rank];
            ++rank;
        }
        dirty = false;
    }
    void print() {
        for (int i = 0; i < rank; ++i) cerr << bitset<64>(span[i]) << endl;
        cerr << endl;
    }
};

#line 1 "math/matrix/xorvector.hpp"
/**
* @brief Xor Vector
* @docs docs/math/matrix/xorvector.md
*/

struct XorVector {
    bool dirty = false;
    int rank, N;
    vector<long long> span;
    XorVector(int N)
        : rank(0), N(N), span(N, 0) {}
    void emplace(ll num) {
        span[rank++] = num;
        dirty        = true;
    }
    bool find(ll num) {
        if (num == 0) return true;
        if (dirty) gaussian_elimination();
        for (int i = 0; i < rank; ++i) {
            if (span[i] == 0LL) break;
            num = min(num, num ^ span[i]);
        }
        return num == 0LL;
    }
    void gaussian_elimination() {
        rank = 0;
        for (int col = 63; col >= 0; --col) {
            int pivot = -1;
            for (int row = rank; row < N; ++row)
                if (span[row] >> col & 1) {
                    pivot = row;
                    break;
                }
            if (pivot == -1) continue;
            swap(span[pivot], span[rank]);
            for (int row = 0; row < N; ++row)
                if (row != rank and span[row] >> col & 1) span[row] ^= span[rank];
            ++rank;
        }
        dirty = false;
    }
    void print() {
        for (int i = 0; i < rank; ++i) cerr << bitset<64>(span[i]) << endl;
        cerr << endl;
    }
};

Back to top page