XOR基底(Linear Basis)
(math/xor_basis.cpp)

• View this file on GitHub
• Last update: 2026-03-12 16:01:52+09:00

説明

整数列から xor 基底を構築する。 基底の本数を $k$ とすると、表現できる値の個数は $2^k$。

できること

• XorBasis<T> xb 空の xor 基底を作る
• int size() 基底の本数を返す
• bool empty() 基底が空なら true
• bool add(T x) x を基底に追加する。独立なら true、追加されなければ false
• bool contains(T x) x を基底で表せるなら true、表せなければ false
• T get_min(T x = 0) x xor y を最小にする y を基底の生成する空間から選んだ結果を返す
• T get_max(T x = 0) x xor y を最大にする y を基底の生成する空間から選んだ結果を返す
• void merge(const XorBasis<T>& other) other の基底を併合する

使い方

add で値を順に入れて使う。 contains(x) で表現可能性を判定でき、get_min(x) と get_max(x) で \(\min_{y \in \langle S \rangle} (x \oplus y), \quad \max_{y \in \langle S \rangle} (x \oplus y)\) を求められる。

実装上の補足

• T は整数型を想定する
• 返り値は x xor y そのものを返す

Verified with

• test/yuki2672_xor_basis.test.cpp

Code

template<class T>
struct XorBasis {
    static_assert(is_integral_v<T>, "XorBasis requires integral T");

    using U = make_unsigned_t<T>;
    static constexpr int B = numeric_limits<U>::digits;

    vector<U> basis;
    int rank = 0;

    XorBasis() : basis(B, 0) {}

    int size() const {
        return rank;
    }

    bool empty() const {
        return rank == 0;
    }

    bool add(T x) {
        U y = reduce_unsigned(static_cast<U>(x));
        if (y == 0) return false;

        int p = B - 1;
        while (((y >> p) & 1) == 0) --p;
        for (int i = 0; i < p; ++i) {
            if ((y >> i) & 1) y ^= basis[i];
        }
        basis[p] = y;
        ++rank;
        for (int i = p + 1; i < B; ++i) {
            if ((basis[i] >> p) & 1) basis[i] ^= y;
        }
        return true;
    }

    bool contains(T x) const {
        return reduce_unsigned(static_cast<U>(x)) == 0;
    }

    T get_min(T x = 0) const {
        return static_cast<T>(reduce_unsigned(static_cast<U>(x)));
    }

    T get_max(T x = 0) const {
        U y = static_cast<U>(x);
        for (int i = B - 1; i >= 0; --i) {
            if (basis[i] == 0) continue;
            U z = y ^ basis[i];
            if (z > y) y = z;
        }
        return static_cast<T>(y);
    }

    void merge(const XorBasis &other) {
        for (int i = 0; i < B; ++i) {
            if (other.basis[i] != 0) add(static_cast<T>(other.basis[i]));
        }
    }

private:
    U reduce_unsigned(U x) const {
        for (int i = B - 1; i >= 0; --i) {
            if (((x >> i) & 1) == 0 || basis[i] == 0) continue;
            x ^= basis[i];
        }
        return x;
    }
};

/**
 * @brief XOR基底(Linear Basis)
 */

#line 1 "math/xor_basis.cpp"
template<class T>
struct XorBasis {
    static_assert(is_integral_v<T>, "XorBasis requires integral T");

    using U = make_unsigned_t<T>;
    static constexpr int B = numeric_limits<U>::digits;

    vector<U> basis;
    int rank = 0;

    XorBasis() : basis(B, 0) {}

    int size() const {
        return rank;
    }

    bool empty() const {
        return rank == 0;
    }

    bool add(T x) {
        U y = reduce_unsigned(static_cast<U>(x));
        if (y == 0) return false;

        int p = B - 1;
        while (((y >> p) & 1) == 0) --p;
        for (int i = 0; i < p; ++i) {
            if ((y >> i) & 1) y ^= basis[i];
        }
        basis[p] = y;
        ++rank;
        for (int i = p + 1; i < B; ++i) {
            if ((basis[i] >> p) & 1) basis[i] ^= y;
        }
        return true;
    }

    bool contains(T x) const {
        return reduce_unsigned(static_cast<U>(x)) == 0;
    }

    T get_min(T x = 0) const {
        return static_cast<T>(reduce_unsigned(static_cast<U>(x)));
    }

    T get_max(T x = 0) const {
        U y = static_cast<U>(x);
        for (int i = B - 1; i >= 0; --i) {
            if (basis[i] == 0) continue;
            U z = y ^ basis[i];
            if (z > y) y = z;
        }
        return static_cast<T>(y);
    }

    void merge(const XorBasis &other) {
        for (int i = 0; i < B; ++i) {
            if (other.basis[i] != 0) add(static_cast<T>(other.basis[i]));
        }
    }

private:
    U reduce_unsigned(U x) const {
        for (int i = B - 1; i >= 0; --i) {
            if (((x >> i) & 1) == 0 || basis[i] == 0) continue;
            x ^= basis[i];
        }
        return x;
    }
};

/**
 * @brief XOR基底(Linear Basis)
 */

Back to top page