sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/matrix_product_mod_2" #include <bits/stdc++.h> #include "../../math/linalg/binary_matrix.hpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M, K; cin >> N >> M >> K; BinaryMatrix<1 << 12> A(N, M), B(M, K); for (int i = 0; i < N; ++i) { string row; cin >> row; for (int j = 0; j < M; ++j) { if (row[j] == '1') A.set(i, j); } } for (int i = 0; i < M; ++i) { string row; cin >> row; for (int j = 0; j < K; ++j) { if (row[j] == '1') B.set(i, j); } } auto C = A.matmul(B); for (int i = 0; i < N; ++i) { for (int j = 0; j < K; ++j) cout << C.get(i, j); cout << "\n"; } }
#line 1 "test/yosupo/matrix_product_mod_2.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/matrix_product_mod_2" #include <bits/stdc++.h> #line 5 "math/linalg/binary_matrix.hpp" /** * @brief Binary Matrix */ template <int SZ> class BinaryMatrix { using Mat = BinaryMatrix; using Vec = std::bitset<SZ>; public: BinaryMatrix() = default; BinaryMatrix(int m, int n) : mat(m), m(m), n(n) {} void set(int i, int j) { mat[i].set(j); } bool get(int i, int j) { return mat[i].test(j); } Mat matmul(const Mat& B) const { Mat res(m, B.n); for (int i = 0; i < m; ++i) { for (int k = 0; k < n; ++k) { if (mat[i][k]) res.mat[i] ^= B.mat[k]; } } return res; } Mat pow(long long k) const { assert(m == n); Mat ret(n, n), A(*this); for (int i = 0; i < n; ++i) { ret.mat[i].set(i); ret.matt[i].set(i); } while (k > 0) { if (k & 1) ret = ret.matmul(A); A = A.matmul(A); k >>= 1; } return ret; } protected: std::vector<Vec> mat; int m, n; }; #line 6 "test/yosupo/matrix_product_mod_2.test.cpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M, K; cin >> N >> M >> K; BinaryMatrix<1 << 12> A(N, M), B(M, K); for (int i = 0; i < N; ++i) { string row; cin >> row; for (int j = 0; j < M; ++j) { if (row[j] == '1') A.set(i, j); } } for (int i = 0; i < M; ++i) { string row; cin >> row; for (int j = 0; j < K; ++j) { if (row[j] == '1') B.set(i, j); } } auto C = A.matmul(B); for (int i = 0; i < N; ++i) { for (int j = 0; j < K; ++j) cout << C.get(i, j); cout << "\n"; } }