test/yosupo/matrix_product_mod_2.test.cpp

• View this file on GitHub
• Last update: 2024-03-02 18:46:36+09:00
• Problem: https://judge.yosupo.jp/problem/matrix_product_mod_2

Depends on

• Binary Matrix (math/linalg/binary_matrix.hpp)

Code

#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";
    }
}

Back to top page