C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
#include "emthrm/math/matrix/binary_matrix/inverse_matrix.hpp"
有限体 $\mathbb{F}_2$ 上の行列である。
template <int N> struct BinaryMatrix;
N
explicit BinaryMatrix(const int m, const int n = N, const bool def = false);
int nrow() const;
int ncol() const;
BinaryMatrix pow(long long exponent) const;
inline const std::bitset<N>& operator[](const int i) const
inline std::bitset<N>& operator[](const int i);
BinaryMatrix& operator=(const BinaryMatrix& x);
BinaryMatrix& operator+=(const BinaryMatrix& x);
BinaryMatrix operator+(const BinaryMatrix& x) const;
BinaryMatrix& operator*=(const BinaryMatrix& x);
BinaryMatrix operator*(const BinaryMatrix& x) const;
template <bool IS_EXTENDED = false, int N>
int gauss_jordan(BinaryMatrix<N>* a);
is_extended
template <int N>
std::vector<bool> linear_equation(const BinaryMatrix<N>& a, const std::vector<bool>& b);
BinaryMatrix<N> inverse_matrix(const BinaryMatrix<N>& a);
#ifndef EMTHRM_MATH_MATRIX_BINARY_MATRIX_INVERSE_MATRIX_HPP_ #define EMTHRM_MATH_MATRIX_BINARY_MATRIX_INVERSE_MATRIX_HPP_ #include <cassert> #include <utility> #include "emthrm/math/matrix/binary_matrix/binary_matrix.hpp" namespace emthrm { template <int N> BinaryMatrix<N> inverse_matrix(const BinaryMatrix<N>& a) { const int n = a.nrow(); BinaryMatrix<N> b(n, n << 1, 0); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { b[i][j] = a[i][j]; } b[i][n + i] = 1; } for (int col = 0; col < n; ++col) { int pivot = -1; for (int row = col; row < n; ++row) { if (b[row][col]) { pivot = row; break; } } if (pivot == -1) return BinaryMatrix<N>(0, 0); std::swap(b[col], b[pivot]); for (int row = 0; row < n; ++row) { if (row != col && b[row][col]) b[row] ^= b[col]; } } BinaryMatrix<N> inv(n, n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { inv[i][j] = b[i][n + j]; } } return inv; } } // namespace emthrm #endif // EMTHRM_MATH_MATRIX_BINARY_MATRIX_INVERSE_MATRIX_HPP_
#line 1 "include/emthrm/math/matrix/binary_matrix/inverse_matrix.hpp" #include <cassert> #include <utility> #line 1 "include/emthrm/math/matrix/binary_matrix/binary_matrix.hpp" #include <bitset> #include <string> #include <vector> namespace emthrm { template <int N> struct BinaryMatrix { explicit BinaryMatrix(const int m, const int n = N, const bool def = false) : n(n), data(m, std::bitset<N>(std::string(n, def ? '1' : '0'))) {} int nrow() const { return data.size(); } int ncol() const { return n; } BinaryMatrix pow(long long exponent) const { BinaryMatrix res(n, n), tmp = *this; for (int i = 0; i < n; ++i) { res[i].set(i); } for (; exponent > 0; exponent >>= 1) { if (exponent & 1) res *= tmp; tmp *= tmp; } return res; } inline const std::bitset<N>& operator[](const int i) const { return data[i]; } inline std::bitset<N>& operator[](const int i) { return data[i]; } BinaryMatrix& operator=(const BinaryMatrix& x) = default; BinaryMatrix& operator+=(const BinaryMatrix& x) { const int m = nrow(); for (int i = 0; i < m; ++i) { data[i] ^= x[i]; } return *this; } BinaryMatrix& operator*=(const BinaryMatrix& x) { const int m = nrow(), l = x.ncol(); BinaryMatrix t_x(l, n), res(m, l); for (int i = 0; i < l; ++i) { for (int j = 0; j < n; ++j) { t_x[i][j] = x[j][i]; } } for (int i = 0; i < m; ++i) { for (int j = 0; j < l; ++j) { if ((data[i] & t_x[j]).count() & 1) res[i].set(j); } } return *this = res; } BinaryMatrix operator+(const BinaryMatrix& x) const { return BinaryMatrix(*this) += x; } BinaryMatrix operator*(const BinaryMatrix& x) const { return BinaryMatrix(*this) *= x; } private: int n; std::vector<std::bitset<N>> data; }; } // namespace emthrm #line 8 "include/emthrm/math/matrix/binary_matrix/inverse_matrix.hpp" namespace emthrm { template <int N> BinaryMatrix<N> inverse_matrix(const BinaryMatrix<N>& a) { const int n = a.nrow(); BinaryMatrix<N> b(n, n << 1, 0); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { b[i][j] = a[i][j]; } b[i][n + i] = 1; } for (int col = 0; col < n; ++col) { int pivot = -1; for (int row = col; row < n; ++row) { if (b[row][col]) { pivot = row; break; } } if (pivot == -1) return BinaryMatrix<N>(0, 0); std::swap(b[col], b[pivot]); for (int row = 0; row < n; ++row) { if (row != col && b[row][col]) b[row] ^= b[col]; } } BinaryMatrix<N> inv(n, n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { inv[i][j] = b[i][n + j]; } } return inv; } } // namespace emthrm