C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title 数学/行列/バイナリ行列/ガウス・ジョルダンの消去法 バイナリ行列版 * * verification-helper: PROBLEM https://yukicoder.me/problems/no/184 */ #include <bitset> #include <iostream> #include "emthrm/math/matrix/binary_matrix/binary_matrix.hpp" #include "emthrm/math/matrix/binary_matrix/gauss_jordan.hpp" int main() { constexpr int B = 61; int n; std::cin >> n; emthrm::BinaryMatrix<B> matrix(n); for (int i = 0; i < n; ++i) { long long a; std::cin >> a; matrix[i] = std::bitset<B>(a); } std::cout << (1LL << emthrm::gauss_jordan(&matrix)) << '\n'; return 0; }
#line 1 "test/math/matrix/binary_matrix/gauss_jordan.test.cpp" /* * @title 数学/行列/バイナリ行列/ガウス・ジョルダンの消去法 バイナリ行列版 * * verification-helper: PROBLEM https://yukicoder.me/problems/no/184 */ #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 12 "test/math/matrix/binary_matrix/gauss_jordan.test.cpp" int main() { constexpr int B = 61; int n; std::cin >> n; emthrm::BinaryMatrix<B> matrix(n); for (int i = 0; i < n; ++i) { long long a; std::cin >> a; matrix[i] = std::bitset<B>(a); } std::cout << (1LL << emthrm::gauss_jordan(&matrix)) << '\n'; return 0; }