linalg/xor/vector_space.hpp

• View this file on GitHub
• Last update: 2025-09-19 11:37:43+09:00
• Include: #include "linalg/xor/vector_space.hpp"

Depends on

• linalg/xor/transpose.hpp

Required by

• alg/monoid/merge_vector_space.hpp

Verified with

• test/2_library_checker/linear_algebra/vector_space_intersection.test.cpp
• test/3_yukicoder/184.test.cpp

Code

#include "linalg/xor/transpose.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{} {}
  Vector_Space(array<UINT, MAX_DIM> dat) : dat(dat) {
    dim = 0;
    FOR(i, MAX_DIM) dim += (dat[i] != 0);
  }

  vc<UINT> to_vec() {
    vc<UINT> ANS;
    FOR(i, MAX_DIM) if (dat[i]) ANS.eb(dat[i]);
    return ANS;
  }

  int size() { return dim; }
  u64 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 v;
  }

  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>);
    Vector_Space<u64, MAX_DIM * 2> z;
    for (auto v : x.dat) {
      if (v) z.add_element(v | static_cast<u64>(v) << MAX_DIM);
    }
    for (auto v : y.dat) {
      if (v) z.add_element(static_cast<u64>(v) << MAX_DIM);
    }
    Vector_Space<UINT, MAX_DIM> ANS;
    for (auto& v : z.dat) {
      if (v <= u32(-1)) ANS.add_element(v);
    }
    return ANS;
  }

  static array<UINT, MAX_DIM> transpose(array<UINT, MAX_DIM> A) {
    constexpr int L = numeric_limits<UINT>::digits;
    array<UINT, L> B;
    FOR(i, MAX_DIM) B[i] = A[i];
    int LOG = 0;
    while ((1 << LOG) < L) ++LOG;
    int width = 1 << LOG;
    UINT mask = -1;
    FOR(t, LOG) {
      width >>= 1;
      mask = mask ^ (mask >> width);
      FOR(i, 1 << t) {
        FOR(j, width) {
          UINT* x = &B[width * (2 * i + 0) + j];
          UINT* y = &B[width * (2 * i + 1) + j];
          *x = ((*y << width) & mask) ^ *x;
          *y = ((*x & mask) >> width) ^ *y;
          *x = ((*y << width) & mask) ^ *x;
        }
      }
    }
    FOR(i, MAX_DIM) A[i] = B[i];
    return A;
  }

  Vector_Space orthogonal_space() {
    array<u64, MAX_DIM> T = transpose(dat);
    array<u64, MAX_DIM> ANS{};
    FOR_R(j, MAX_DIM) {
      if (T[j] >> j & 1) continue;
      ANS[j] = (UINT(1) << j) | T[j];
    }
    return Vector_Space(ANS);
  }
};

#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{} {}
  Vector_Space(array<UINT, MAX_DIM> dat) : dat(dat) {
    dim = 0;
    FOR(i, MAX_DIM) dim += (dat[i] != 0);
  }

  vc<UINT> to_vec() {
    vc<UINT> ANS;
    FOR(i, MAX_DIM) if (dat[i]) ANS.eb(dat[i]);
    return ANS;
  }

  int size() { return dim; }
  u64 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 v;
  }

  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>);
    Vector_Space<u64, MAX_DIM * 2> z;
    for (auto v : x.dat) {
      if (v) z.add_element(v | static_cast<u64>(v) << MAX_DIM);
    }
    for (auto v : y.dat) {
      if (v) z.add_element(static_cast<u64>(v) << MAX_DIM);
    }
    Vector_Space<UINT, MAX_DIM> ANS;
    for (auto& v : z.dat) {
      if (v <= u32(-1)) ANS.add_element(v);
    }
    return ANS;
  }

  static array<UINT, MAX_DIM> transpose(array<UINT, MAX_DIM> A) {
    constexpr int L = numeric_limits<UINT>::digits;
    array<UINT, L> B;
    FOR(i, MAX_DIM) B[i] = A[i];
    int LOG = 0;
    while ((1 << LOG) < L) ++LOG;
    int width = 1 << LOG;
    UINT mask = -1;
    FOR(t, LOG) {
      width >>= 1;
      mask = mask ^ (mask >> width);
      FOR(i, 1 << t) {
        FOR(j, width) {
          UINT* x = &B[width * (2 * i + 0) + j];
          UINT* y = &B[width * (2 * i + 1) + j];
          *x = ((*y << width) & mask) ^ *x;
          *y = ((*x & mask) >> width) ^ *y;
          *x = ((*y << width) & mask) ^ *x;
        }
      }
    }
    FOR(i, MAX_DIM) A[i] = B[i];
    return A;
  }

  Vector_Space orthogonal_space() {
    array<u64, MAX_DIM> T = transpose(dat);
    array<u64, MAX_DIM> ANS{};
    FOR_R(j, MAX_DIM) {
      if (T[j] >> j & 1) continue;
      ANS[j] = (UINT(1) << j) | T[j];
    }
    return Vector_Space(ANS);
  }
};

Back to top page