linalg/xor/solve_linear.hpp

• View this file on GitHub
• Last update: 2025-10-13 19:02:32+09:00
• Include: #include "linalg/xor/solve_linear.hpp"

Depends on

• linalg/xor/transpose.hpp

Code

#include "linalg/xor/transpose.hpp"

template <typename UINT>
vc<UINT> solve_linear(int n, int m, vc<UINT> A, UINT b) {
  vc<UINT> mat(m);
  UINT rhs = 0;

  FOR(i, len(A)) {
    UINT a = A[i];
    UINT c = b >> i & 1;
    FOR_R(j, m) {
      if (chmin(a, a ^ mat[j])) {
        c ^= (rhs >> j & 1);
      }
    }
    if (a == 0 && c) return {};
    if (a) {
      int k = topbit(a);
      FOR(j, k, m) {
        if (chmin(mat[j], mat[j] ^ a)) rhs ^= c << j;
      }
      mat[k] = a, rhs |= c << k;
    }
  }

  vc<UINT> ANS = {rhs};
  mat = transpose(m, m, mat, 0);
  FOR(i, m) {
    if (!(mat[i] >> i & 1)) ANS.eb(mat[i] | UINT(1) << i);
  }
  return 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/solve_linear.hpp"

template <typename UINT>
vc<UINT> solve_linear(int n, int m, vc<UINT> A, UINT b) {
  vc<UINT> mat(m);
  UINT rhs = 0;

  FOR(i, len(A)) {
    UINT a = A[i];
    UINT c = b >> i & 1;
    FOR_R(j, m) {
      if (chmin(a, a ^ mat[j])) {
        c ^= (rhs >> j & 1);
      }
    }
    if (a == 0 && c) return {};
    if (a) {
      int k = topbit(a);
      FOR(j, k, m) {
        if (chmin(mat[j], mat[j] ^ a)) rhs ^= c << j;
      }
      mat[k] = a, rhs |= c << k;
    }
  }

  vc<UINT> ANS = {rhs};
  mat = transpose(m, m, mat, 0);
  FOR(i, m) {
    if (!(mat[i] >> i & 1)) ANS.eb(mat[i] | UINT(1) << i);
  }
  return ANS;
}

Back to top page