Binary Basis
(lib/math/binarybasis.hpp)

• View this file on GitHub
• Last update: 2025-06-02 01:41:54+09:00
• Include: #include "lib/math/binarybasis.hpp"

Binary Basis

概要

数の集合に対する XOR 基底を求めます。

使い方

• BinaryBasis(vec): 集合 vec について、XOR 基底を求めます。
• add(x): $x$ を基底の集合に追加します。
• exist(x): 基底の集合の中から XOR を繰り返して $x$ を作れるかどうかを判定します。
• normalize(): 基底の集合を整理します。
• kth_element(k): 基底から生成できる数の集合の $k$ 番目を取得します。(0-indexed なことに注意)
• size(x): 基底の集合の大きさを取得します。

計算量

集合の中の最大値を $A$ とします。

• BinaryBasis(vec): vec の要素数を $N$ とすると、$\mathrm{O}(N \log A)$
• add(x): $\mathrm{O}(\log A)$
• exist(x): $\mathrm{O}(\log A)$
• normalize(): $\mathrm{O}(\log^2 A)$
• kth_element(k): $\mathrm{O}(\log A)$
• size(x): $\mathrm{O}(1)$

Verified with

• test/yukicoder/yuki_184.test.cpp

Code

#pragma once

/**
 * @brief Binary Basis
 * @docs docs/math/binarybasis.md
 */

template <typename T>
struct BinaryBasis{

    vector<T> basis, original, inds;
    BinaryBasis(){};
    BinaryBasis(const vector<T> &vec){
        for(auto x : vec){
            int len = basis.size();
            T v = (T) 1 << (len);
            T y = x;
            for(int i = 0; i < len; i++){
                if((y ^ basis[i]) < y){
                    y ^= basis[i];
                    v ^= inds[i];
                }
            }
            if(y > 0){
                basis.push_back(y);
                original.push_back(x);
                inds.push_back(v);
            }
        }
        normalize();
    }

    pair<T, T> add(const T &x){
        int len = basis.size();
        T v = (T) 1 << (len);
        T y = x;
        for(int i = 0; i < len; i++){
            if((y ^ basis[i]) < y){
                y ^= basis[i];
                v ^= inds[i];
            }
        }
        if(y > 0){
            basis.push_back(y);
            original.push_back(x);
            inds.push_back(v);
        }
        return make_pair(y, v);
    }

    void normalize(){
        int len = basis.size();
        for(int i = 0; i < len; i++){
            for(int j = i + 1; j < len; j++){
                if(basis[j] < basis[i]){
                    swap(basis[i], basis[j]);
                    swap(original[i], original[j]);
                    swap(inds[i], inds[j]);
                }
            }
        }
        for(int i = 0; i < (int) basis.size(); ++i){
            for(int j = 0; j < i; ++j){
                if((basis[i] ^ basis[j]) < basis[i]){
                    basis[i] ^= basis[j];
                    inds[i] ^= inds[j];
                }
            }
        }
    }

    bool exist(const T &x){
        T y = x;
        for(auto z : basis){
            y = min(y, y ^ z);
        }
        return y == 0;
    }

    T getInd(const T &x){
        int len = basis.size();
        T v = T(0);
        T y = x;
        for(int i = 0; i < len; i++){
            if((y ^ basis[i]) < y){
                y ^= basis[i];
                v ^= inds[i];
            }
        }
        if(y > 0) return -1;
        return v;
    }

    T kth_element(const long long &k){
        T res = 0;
        for(int i = 0; i < (int) basis.size(); ++i){
            if(k & (1LL << i)){
                res ^= basis[i];
            }
        }
        return res;
    }

    size_t size(){
        return basis.size();
    }
};

#line 2 "lib/math/binarybasis.hpp"

/**
 * @brief Binary Basis
 * @docs docs/math/binarybasis.md
 */

template <typename T>
struct BinaryBasis{

    vector<T> basis, original, inds;
    BinaryBasis(){};
    BinaryBasis(const vector<T> &vec){
        for(auto x : vec){
            int len = basis.size();
            T v = (T) 1 << (len);
            T y = x;
            for(int i = 0; i < len; i++){
                if((y ^ basis[i]) < y){
                    y ^= basis[i];
                    v ^= inds[i];
                }
            }
            if(y > 0){
                basis.push_back(y);
                original.push_back(x);
                inds.push_back(v);
            }
        }
        normalize();
    }

    pair<T, T> add(const T &x){
        int len = basis.size();
        T v = (T) 1 << (len);
        T y = x;
        for(int i = 0; i < len; i++){
            if((y ^ basis[i]) < y){
                y ^= basis[i];
                v ^= inds[i];
            }
        }
        if(y > 0){
            basis.push_back(y);
            original.push_back(x);
            inds.push_back(v);
        }
        return make_pair(y, v);
    }

    void normalize(){
        int len = basis.size();
        for(int i = 0; i < len; i++){
            for(int j = i + 1; j < len; j++){
                if(basis[j] < basis[i]){
                    swap(basis[i], basis[j]);
                    swap(original[i], original[j]);
                    swap(inds[i], inds[j]);
                }
            }
        }
        for(int i = 0; i < (int) basis.size(); ++i){
            for(int j = 0; j < i; ++j){
                if((basis[i] ^ basis[j]) < basis[i]){
                    basis[i] ^= basis[j];
                    inds[i] ^= inds[j];
                }
            }
        }
    }

    bool exist(const T &x){
        T y = x;
        for(auto z : basis){
            y = min(y, y ^ z);
        }
        return y == 0;
    }

    T getInd(const T &x){
        int len = basis.size();
        T v = T(0);
        T y = x;
        for(int i = 0; i < len; i++){
            if((y ^ basis[i]) < y){
                y ^= basis[i];
                v ^= inds[i];
            }
        }
        if(y > 0) return -1;
        return v;
    }

    T kth_element(const long long &k){
        T res = 0;
        for(int i = 0; i < (int) basis.size(); ++i){
            if(k & (1LL << i)){
                res ^= basis[i];
            }
        }
        return res;
    }

    size_t size(){
        return basis.size();
    }
};

Back to top page