linalg/xor/basis.hpp

• View this file on GitHub
• Last update: 2026-07-26 20:34:09+09:00
• Include: #include "linalg/xor/basis.hpp"

Depends on

• other/bit.hpp

Required by

• nt/nimber/solve_quadratic.hpp

Verified with

• test/1_mytest/nimber.test.cpp
• test/3_yukicoder/2895.test.cpp

Code

#include "other/bit.hpp"

// basis[i]: i 番目に追加成功したもの. 別のラベルがあるなら外で管理する.
// array<UINT, MAX_DIM> rbasis: 上三角化された基底. [i][i]==1.
// way<UINT,UINT> rbasis[i] を basis[j] で作る方法
template <int MAX_DIM>
struct Basis {
  static_assert(MAX_DIM <= 128);
  using UINT = conditional_t<(MAX_DIM <= 32), u32,
                             conditional_t<(MAX_DIM <= 64), u64, u128>>;
  int rank;
  array<UINT, MAX_DIM> basis;
  array<UINT, MAX_DIM> rbasis;
  array<UINT, MAX_DIM> way;
  Basis() : rank(0), basis{}, rbasis{}, way{} {}

  // return : (sum==x にできるか, その方法)
  pair<bool, UINT> solve(UINT x) {
    UINT c = 0;
    FOR(i, MAX_DIM) {
      if ((x >> i & 1) && (rbasis[i] != 0)) {
        c ^= way[i], x ^= rbasis[i];
      }
    }
    if (x == 0) return {true, c};
    return {false, 0};
  }

  // return : (sum==x にできるか, その方法). false の場合には追加する
  pair<bool, UINT> solve_or_add(UINT x) {
    UINT y = x, c = 0;
    FOR(i, MAX_DIM) {
      if ((x >> i & 1) && (rbasis[i] != 0)) {
        c ^= way[i], x ^= rbasis[i];
      }
    }
    if (x == 0) return {true, c};
    int k = lowbit(x);
    basis[rank] = y, rbasis[k] = x, way[k] = c | UINT(1) << rank, ++rank;
    return {false, 0};
  }
};

#line 2 "other/bit.hpp"

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(unsigned(x)) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T kth_bit(int k) {
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  UINT s;
  struct iter {
    UINT s;
    int operator*() const { return lowbit(s); }
    void operator++() { s &= s - 1; }
    bool operator!=(nullptr_t) const { return s; }
  };
  iter begin() const { return {s}; }
  nullptr_t end() const { return nullptr; }
};

template <typename UINT>
struct all_subset {
  UINT s;
  struct iter {
    UINT s, t;
    bool done = false;
    UINT operator*() const { return t; }
    void operator++() {
      done = (t == 0);
      t = (t - 1) & s;
    }
    bool operator!=(nullptr_t) const { return !done; }
  };
  iter begin() const { return {s, s}; }
  nullptr_t end() const { return nullptr; }
};

constexpr u64 full_mask(int n) { return n == 64 ? -1ULL : (1ULL << n) - 1; }
#line 2 "linalg/xor/basis.hpp"

// basis[i]: i 番目に追加成功したもの. 別のラベルがあるなら外で管理する.
// array<UINT, MAX_DIM> rbasis: 上三角化された基底. [i][i]==1.
// way<UINT,UINT> rbasis[i] を basis[j] で作る方法
template <int MAX_DIM>
struct Basis {
  static_assert(MAX_DIM <= 128);
  using UINT = conditional_t<(MAX_DIM <= 32), u32,
                             conditional_t<(MAX_DIM <= 64), u64, u128>>;
  int rank;
  array<UINT, MAX_DIM> basis;
  array<UINT, MAX_DIM> rbasis;
  array<UINT, MAX_DIM> way;
  Basis() : rank(0), basis{}, rbasis{}, way{} {}

  // return : (sum==x にできるか, その方法)
  pair<bool, UINT> solve(UINT x) {
    UINT c = 0;
    FOR(i, MAX_DIM) {
      if ((x >> i & 1) && (rbasis[i] != 0)) {
        c ^= way[i], x ^= rbasis[i];
      }
    }
    if (x == 0) return {true, c};
    return {false, 0};
  }

  // return : (sum==x にできるか, その方法). false の場合には追加する
  pair<bool, UINT> solve_or_add(UINT x) {
    UINT y = x, c = 0;
    FOR(i, MAX_DIM) {
      if ((x >> i & 1) && (rbasis[i] != 0)) {
        c ^= way[i], x ^= rbasis[i];
      }
    }
    if (x == 0) return {true, c};
    int k = lowbit(x);
    basis[rank] = y, rbasis[k] = x, way[k] = c | UINT(1) << rank, ++rank;
    return {false, 0};
  }
};

Back to top page