rcpl

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ruthen71/rcpl

:warning: Matrix (行列)
(data_structure/matrix.hpp)

Code

#pragma once

template <class T> struct Matrix {
    std::vector<std::vector<T>> A;

    Matrix(int N) : A(N, std::vector<T>(N, T(0))) {}
    Matrix(int N, int M, T val = T(0)) : A(N, std::vector<T>(M, val)) {}

    inline size_t size() const { return A.size(); }

    inline int row() const { return (int)A.size(); }

    inline int col() const { return (int)A[0].size(); }

    inline const std::vector<T> &operator[](int i) const { return A[i]; }  // read

    inline std::vector<T> &operator[](int i) { return A[i]; }  // write

    static Matrix E(int N) {
        Matrix ret(N);
        for (int i = 0; i < N; i++) ret[i][i] = T(1);
        return ret;
    }

    Matrix &operator+=(const Matrix &B) {
        int N = row(), M = col();
        assert(N == B.row() and M == B.col());
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                (*this)[i][j] += B[i][j];
            }
        }
        return (*this);
    }

    Matrix &operator-=(const Matrix &B) {
        int N = row(), M = col();
        assert(N == B.row() and M == B.col());
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                (*this)[i][j] -= B[i][j];
            }
        }
        return (*this);
    }

    Matrix &operator*=(const Matrix &B) {
        int N = row(), M = B.col(), L = B.row();
        assert(L == col());
        Matrix C(N, M);
        for (int i = 0; i < N; i++) {
            for (int k = 0; k < L; k++) {
                for (int j = 0; j < M; j++) {
                    C[i][j] += (*this)[i][k] * B[k][j];
                }
            }
        }
        A.swap(C.A);
        return (*this);
    }

    // A ^= k
    Matrix pow(long long k) {
        assert(row() == col());
        Matrix B = Matrix::E(row()), X = (*this);
        while (k) {
            if (k & 1) B *= X;
            X *= X;
            k >>= 1;
        }
        A.swap(B.A);
        return (*this);
    }

    Matrix operator+(const Matrix &B) { return ((*this) += B); }

    Matrix operator-(const Matrix &B) { return ((*this) -= B); }

    Matrix operator*(const Matrix &B) { return ((*this) *= B); }

    friend std::ostream &operator<<(std::ostream &os, Matrix &A) {
        int N = A.row(), M = A.col();
        for (int i = 0; i < N; i++) {
            os << '[';
            for (int j = 0; j < M; j++) os << A[i][j] << " \n"[j == M - 1];
        }
        return (os);
    }

    Matrix &operator+=(const T &k) {
        int N = row(), M = col();
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++) (*this)[i][j] += k;
        return (*this);
    }

    Matrix &operator-=(const T &k) {
        int N = row(), M = col();
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++) (*this)[i][j] -= k;
        return (*this);
    }

    Matrix &operator*=(const T &k) {
        int N = row(), M = col();
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++) (*this)[i][j] *= k;
        return (*this);
    }

    Matrix &operator/=(const T &k) {
        int N = row(), M = col();
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++) (*this)[i][j] /= k;
        return (*this);
    }

    Matrix operator+(const T &k) { return ((*this) += k); }

    Matrix operator-(const T &k) { return ((*this) -= k); }

    Matrix operator*(const T &k) { return ((*this) *= k); }

    Matrix operator/(const T &k) { return ((*this) /= k); }
};
#line 2 "data_structure/matrix.hpp"

template <class T> struct Matrix {
    std::vector<std::vector<T>> A;

    Matrix(int N) : A(N, std::vector<T>(N, T(0))) {}
    Matrix(int N, int M, T val = T(0)) : A(N, std::vector<T>(M, val)) {}

    inline size_t size() const { return A.size(); }

    inline int row() const { return (int)A.size(); }

    inline int col() const { return (int)A[0].size(); }

    inline const std::vector<T> &operator[](int i) const { return A[i]; }  // read

    inline std::vector<T> &operator[](int i) { return A[i]; }  // write

    static Matrix E(int N) {
        Matrix ret(N);
        for (int i = 0; i < N; i++) ret[i][i] = T(1);
        return ret;
    }

    Matrix &operator+=(const Matrix &B) {
        int N = row(), M = col();
        assert(N == B.row() and M == B.col());
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                (*this)[i][j] += B[i][j];
            }
        }
        return (*this);
    }

    Matrix &operator-=(const Matrix &B) {
        int N = row(), M = col();
        assert(N == B.row() and M == B.col());
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                (*this)[i][j] -= B[i][j];
            }
        }
        return (*this);
    }

    Matrix &operator*=(const Matrix &B) {
        int N = row(), M = B.col(), L = B.row();
        assert(L == col());
        Matrix C(N, M);
        for (int i = 0; i < N; i++) {
            for (int k = 0; k < L; k++) {
                for (int j = 0; j < M; j++) {
                    C[i][j] += (*this)[i][k] * B[k][j];
                }
            }
        }
        A.swap(C.A);
        return (*this);
    }

    // A ^= k
    Matrix pow(long long k) {
        assert(row() == col());
        Matrix B = Matrix::E(row()), X = (*this);
        while (k) {
            if (k & 1) B *= X;
            X *= X;
            k >>= 1;
        }
        A.swap(B.A);
        return (*this);
    }

    Matrix operator+(const Matrix &B) { return ((*this) += B); }

    Matrix operator-(const Matrix &B) { return ((*this) -= B); }

    Matrix operator*(const Matrix &B) { return ((*this) *= B); }

    friend std::ostream &operator<<(std::ostream &os, Matrix &A) {
        int N = A.row(), M = A.col();
        for (int i = 0; i < N; i++) {
            os << '[';
            for (int j = 0; j < M; j++) os << A[i][j] << " \n"[j == M - 1];
        }
        return (os);
    }

    Matrix &operator+=(const T &k) {
        int N = row(), M = col();
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++) (*this)[i][j] += k;
        return (*this);
    }

    Matrix &operator-=(const T &k) {
        int N = row(), M = col();
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++) (*this)[i][j] -= k;
        return (*this);
    }

    Matrix &operator*=(const T &k) {
        int N = row(), M = col();
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++) (*this)[i][j] *= k;
        return (*this);
    }

    Matrix &operator/=(const T &k) {
        int N = row(), M = col();
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++) (*this)[i][j] /= k;
        return (*this);
    }

    Matrix operator+(const T &k) { return ((*this) += k); }

    Matrix operator-(const T &k) { return ((*this) -= k); }

    Matrix operator*(const T &k) { return ((*this) *= k); }

    Matrix operator/(const T &k) { return ((*this) /= k); }
};
Back to top page