alg/monoid/merge_vector_space.hpp

• View this file on GitHub
• Last update: 2025-09-18 21:29:06+09:00
• Include: #include "alg/monoid/merge_vector_space.hpp"
• Link: View error logs on GitHub Actions

Depends on

• linalg/xor/transpose.hpp
• linalg/xor/vector_space.hpp

Verified with

• test/3_yukicoder/184.test.cpp

Code

#include "linalg/xor/vector_space.hpp"

template <typename UINT>
struct Merge_Vector_Space {
  using value_type = Vector_Space<UINT>;
  using X = value_type;
  static X op(X x, X y) { return Vector_Space<UINT>::merge(x, y); }
  static constexpr X unit() { return {}; }
  static constexpr bool commute = 1;
};

#line 2 "linalg/xor/transpose.hpp"

// n x m 行列の transpose。O((n+m)log(n+m)) 時間。
// https://github.com/dsnet/matrix-transpose
template <typename UINT>
vc<UINT> transpose(int n, int m, vc<UINT>& A, bool keep_A = 1) {
  assert(max(n, m) <= numeric_limits<UINT>::digits);
  assert(len(A) == n);
  vc<UINT> tmp;
  if (keep_A) tmp = A;
  int LOG = 0;
  while ((1 << LOG) < max(n, m)) ++LOG;
  A.resize(1 << LOG);
  int width = 1 << LOG;
  UINT mask = 1;
  FOR(i, LOG) mask = mask | (mask << (1 << i));
  FOR(t, LOG) {
    width >>= 1;
    mask = mask ^ (mask >> width);
    FOR(i, 1 << t) {
      FOR(j, width) {
        UINT* x = &A[width * (2 * i + 0) + j];
        UINT* y = &A[width * (2 * i + 1) + j];
        *x = ((*y << width) & mask) ^ *x;
        *y = ((*x & mask) >> width) ^ *y;
        *x = ((*y << width) & mask) ^ *x;
      }
    }
  }
  A.resize(m);
  if (!keep_A) return A;
  swap(A, tmp);
  return tmp;
}
#line 2 "linalg/xor/vector_space.hpp"

template <typename UINT, int MAX_DIM>
struct Vector_Space {
  static_assert(is_same_v<UINT, u32> || is_same_v<UINT, u64> ||
                is_same_v<UINT, u128>);
  int dim;
  array<UINT, MAX_DIM> dat;

  Vector_Space() : dim(0), dat{} {}

  bool add_element(UINT v) {
    FOR_R(i, MAX_DIM) { chmin(v, v ^ dat[i]); }
    if (v == 0) return 0;
    FOR(i, MAX_DIM) {
      if (dat[i] != 0) chmin(dat[i], dat[i] ^ v);
    }
    dat[topbit(v)] = v;
    ++dim;
    return true;
  }

  bool contain(UINT v) {
    for (UINT w : dat) {
      chmin(v, v ^ w);
    }
    return v == 0;
  }

  UINT lower_bound(UINT x) {
    int d = dim;
    u32 ans = 0, now = 0;
    FOR_R(i, MAX_DIM) {
      if (dat[i] == 0) continue;
      --d;
      SHOW(now, ans, dat[i], x);
      if ((now ^ dat[i]) < x) {
        ans += UINT(1) << d;
        now ^= dat[i];
      }
    }
    if (now < x) ans += 1;
    return ans;
  }

  UINT kth(UINT k) {
    assert(k < (UINT(1) << dim));
    int d = 0;
    UINT ans = 0;
    FOR(i, MAX_DIM) {
      if (dat[i] == 0) continue;
      if (k >> d & 1) ans ^= dat[i];
      ++d;
    }
    return ans;
  }

  UINT get_max(UINT xor_val = 0) {
    UINT res = xor_val;
    for (auto&& x : dat) chmax(res, res ^ x);
    return res;
  }

  UINT get_min(UINT xor_val = 0) {
    UINT res = xor_val;
    for (auto&& x : dat) chmin(res, res ^ x);
    return res;
  }

  static Vector_Space merge(Vector_Space x, Vector_Space y) {
    if (len(x) < len(y)) swap(x, y);
    for (auto v : y.dat) {
      x.add_element(v);
    }
    return x;
  }

  static Vector_Space intersection(Vector_Space& x, Vector_Space& y) {
    // とりあえず
    static_assert(is_same_v<UINT, u32>);
    vc<u64> xx;
    for (auto& v : x.dat) xx.eb(v | static_cast<u64>(v) << 32);
    Vector_Space<u64, MAX_DIM * 2> z(xx, true);
    for (auto& v : y.dat) z.add_element(static_cast<u64>(v) << 32);
    Vector_Space<UINT, MAX_DIM> ANS;
    for (auto& v : z.dat) {
      if (v <= u32(-1)) ANS.add_element(v);
    }
    return ANS;
  }
};
#line 2 "alg/monoid/merge_vector_space.hpp"

template <typename UINT>
struct Merge_Vector_Space {
  using value_type = Vector_Space<UINT>;
  using X = value_type;
  static X op(X x, X y) { return Vector_Space<UINT>::merge(x, y); }
  static constexpr X unit() { return {}; }
  static constexpr bool commute = 1;
};

Back to top page