linalg/xor/mat_inv.hpp

• View this file on GitHub
• Last update: 2023-02-03 10:57:37+09:00
• Include: #include "linalg/xor/mat_inv.hpp"

Verified with

• test/mytest/QOJ5445.test.cpp

Code

// 行ベクトルを整数型で表現
template <typename UINT>
vc<UINT> mat_inv(vc<UINT> A) {
  const int N = len(A);
  vc<UINT> B(N);
  FOR(i, N) B[i] = u64(1) << i;
  FOR(i, N) FOR(j, N) if (j != i) {
    if (chmin(A[i], A[i] ^ A[j])) B[i] ^= B[j];
  }
  vc<UINT> res(N);
  FOR(i, N) res[topbit(A[i])] = B[i];
  return res;
}

#line 1 "linalg/xor/mat_inv.hpp"
// 行ベクトルを整数型で表現
template <typename UINT>
vc<UINT> mat_inv(vc<UINT> A) {
  const int N = len(A);
  vc<UINT> B(N);
  FOR(i, N) B[i] = u64(1) << i;
  FOR(i, N) FOR(j, N) if (j != i) {
    if (chmin(A[i], A[i] ^ A[j])) B[i] ^= B[j];
  }
  vc<UINT> res(N);
  FOR(i, N) res[topbit(A[i])] = B[i];
  return res;
}

Back to top page