C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title 数学/行列/バイナリ行列/逆行列 バイナリ行列版 * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2624 */ #include <bitset> #include <iostream> #include "emthrm/math/matrix/binary_matrix/binary_matrix.hpp" #include "emthrm/math/matrix/binary_matrix/gauss_jordan.hpp" #include "emthrm/math/matrix/binary_matrix/inverse_matrix.hpp" int main() { constexpr int N = 600; using binary_matrix = emthrm::BinaryMatrix<N>; int n; std::cin >> n; binary_matrix a(n, n), v(n, 1); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int a_ij; std::cin >> a_ij; a[i][j] = a_ij; } } for (int i = 0; i < n; ++i) { int v_i; std::cin >> v_i; v[i][0] = v_i; } int t; std::cin >> t; binary_matrix inv = emthrm::inverse_matrix(a); if (inv.nrow() == 0) { a = a.pow(t); binary_matrix av(n, n + 1); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { av[i][j] = a[i][j]; } av[i][n] = v[i][0]; } std::cout << (emthrm::gauss_jordan(&a) == emthrm::gauss_jordan(&av) ? "ambiguous\n" : "none\n"); } else { inv = inv.pow(t) * v; for (int i = 0; i < n; ++i) { std::cout << inv[i][0] << " \n"[i + 1 == n]; } } return 0; }
#line 1 "test/math/matrix/binary_matrix/inverse_matrix.test.cpp" /* * @title 数学/行列/バイナリ行列/逆行列 バイナリ行列版 * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2624 */ #include <bitset> #include <iostream> #line 1 "include/emthrm/math/matrix/binary_matrix/binary_matrix.hpp" #line 5 "include/emthrm/math/matrix/binary_matrix/binary_matrix.hpp" #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 1 "include/emthrm/math/matrix/binary_matrix/gauss_jordan.hpp" #include <utility> #line 7 "include/emthrm/math/matrix/binary_matrix/gauss_jordan.hpp" namespace emthrm { template <bool IS_EXTENDED = false, int N> int gauss_jordan(BinaryMatrix<N>* a) { const int m = a->nrow(), n = a->ncol(); int rank = 0; for (int col = 0; col < (IS_EXTENDED ? n - 1 : n); ++col) { int pivot = -1; for (int row = rank; row < m; ++row) { if ((*a)[row][col]) { pivot = row; break; } } if (pivot == -1) continue; std::swap((*a)[rank], (*a)[pivot]); for (int row = 0; row < m; ++row) { if (row != rank && (*a)[row][col]) (*a)[row] ^= (*a)[rank]; } ++rank; } return rank; } } // namespace emthrm #line 1 "include/emthrm/math/matrix/binary_matrix/inverse_matrix.hpp" #include <cassert> #line 6 "include/emthrm/math/matrix/binary_matrix/inverse_matrix.hpp" #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 #line 13 "test/math/matrix/binary_matrix/inverse_matrix.test.cpp" int main() { constexpr int N = 600; using binary_matrix = emthrm::BinaryMatrix<N>; int n; std::cin >> n; binary_matrix a(n, n), v(n, 1); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int a_ij; std::cin >> a_ij; a[i][j] = a_ij; } } for (int i = 0; i < n; ++i) { int v_i; std::cin >> v_i; v[i][0] = v_i; } int t; std::cin >> t; binary_matrix inv = emthrm::inverse_matrix(a); if (inv.nrow() == 0) { a = a.pow(t); binary_matrix av(n, n + 1); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { av[i][j] = a[i][j]; } av[i][n] = v[i][0]; } std::cout << (emthrm::gauss_jordan(&a) == emthrm::gauss_jordan(&av) ? "ambiguous\n" : "none\n"); } else { inv = inv.pow(t) * v; for (int i = 0; i < n; ++i) { std::cout << inv[i][0] << " \n"[i + 1 == n]; } } return 0; }