基底 (basis)
(include/emthrm/math/basis.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/math/basis.hpp"

仕様

template <int D>
struct Basis;

• D：ビット幅

メンバ変数

名前	説明
std::vector<std::bitset<D>> v	ベクトル空間
std::vector<int> msb	$i$ 番目のベクトルの最上位ビット

メンバ関数

名前	効果・戻り値
Basis();	デフォルトコンストラクタ
bool add(std::bitset<D> val);	ベクトル $\mathrm{val}$ を加えたのち、実際に要素数が増えたかを返す。
int rank() const;	要素数
inline bool operator<(const Basis& x) const;

参考文献

• http://www.kupc.jp/static/media/K.290ca2fd.pdf
• https://xuzijian629.hatenablog.com/entry/2019/10/30/013225
• https://atcoder.jp/contests/kupc2012/submissions/7660727

TODO

• https://noshi91.hatenablog.com/entry/2023/12/06/002723

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/2416/review/5214392/emthrm/C++17

Verified with

• 数学/基底 (test/math/basis.test.cpp)

Code

#ifndef EMTHRM_MATH_BASIS_HPP_
#define EMTHRM_MATH_BASIS_HPP_

#include <algorithm>
#include <bitset>
#include <iterator>
#include <vector>

namespace emthrm {

template <int D>
struct Basis {
  std::vector<std::bitset<D>> v;
  std::vector<int> msb;

  Basis() = default;

  bool add(std::bitset<D> val) {
    const int n = rank();
    if (n == D) return false;
    for (int i = 0; i < n; ++i) {
      if (val[msb[i]]) val ^= v[i];
    }
    if (val.none()) return false;
    int m = D - 1;
    while (!val[m]) --m;
    if (v.empty()) [[unlikely]] {
      v.emplace_back(val);
      msb.emplace_back(m);
      return true;
    }
    const int idx = std::distance(std::upper_bound(msb.rbegin(), msb.rend(), m),
                                  msb.rend());
    v.emplace(std::next(v.begin(), idx), val);
    msb.emplace(std::next(msb.begin(), idx), m);
    for (int i = idx + 1; i <= n; ++i) {
      if (v[idx][msb[i]]) v[idx] ^= v[i];
    }
    for (int i = idx - 1; i >= 0; --i) {
      if (v[i][m]) v[i] ^= v[idx];
    }
    return true;
  }

  int rank() const { return v.size(); }

  inline bool operator<(const Basis& x) const {
    const int n = v.size();
    if (n != x.rank()) return n < x.rank();
    if (n == D) return false;
    for (int i = 0; i < n; ++i) {
      if (msb[i] != x.msb[i]) return msb[i] < x.msb[i];
    }
    for (int i = 0; i < n; ++i) {
      for (int j = msb[i] - 1; ; --j) {
        if (v[i][j] != x.v[i][j]) return x.v[i][j];
      }
    }
    return false;
  }
};

}  // namespace emthrm

#endif  // EMTHRM_MATH_BASIS_HPP_

#line 1 "include/emthrm/math/basis.hpp"



#include <algorithm>
#include <bitset>
#include <iterator>
#include <vector>

namespace emthrm {

template <int D>
struct Basis {
  std::vector<std::bitset<D>> v;
  std::vector<int> msb;

  Basis() = default;

  bool add(std::bitset<D> val) {
    const int n = rank();
    if (n == D) return false;
    for (int i = 0; i < n; ++i) {
      if (val[msb[i]]) val ^= v[i];
    }
    if (val.none()) return false;
    int m = D - 1;
    while (!val[m]) --m;
    if (v.empty()) [[unlikely]] {
      v.emplace_back(val);
      msb.emplace_back(m);
      return true;
    }
    const int idx = std::distance(std::upper_bound(msb.rbegin(), msb.rend(), m),
                                  msb.rend());
    v.emplace(std::next(v.begin(), idx), val);
    msb.emplace(std::next(msb.begin(), idx), m);
    for (int i = idx + 1; i <= n; ++i) {
      if (v[idx][msb[i]]) v[idx] ^= v[i];
    }
    for (int i = idx - 1; i >= 0; --i) {
      if (v[i][m]) v[i] ^= v[idx];
    }
    return true;
  }

  int rank() const { return v.size(); }

  inline bool operator<(const Basis& x) const {
    const int n = v.size();
    if (n != x.rank()) return n < x.rank();
    if (n == D) return false;
    for (int i = 0; i < n; ++i) {
      if (msb[i] != x.msb[i]) return msb[i] < x.msb[i];
    }
    for (int i = 0; i < n; ++i) {
      for (int j = msb[i] - 1; ; --j) {
        if (v[i][j] != x.v[i][j]) return x.v[i][j];
      }
    }
    return false;
  }
};

}  // namespace emthrm

Back to top page