monoids/matrix_template.hpp

View this file on GitHub
Last update: 2021-08-30 05:56:51+09:00
Include: #include "monoids/matrix_template.hpp"

Depends on

Code

#pragma once
#include "../number/matrix_template.hpp"

template <class T, int N>
struct matrix_monoid {
    typedef matrix<T, N, N> value_type;
    value_type f;
    value_type unit() const {
        return unit_matrix<T, N>();
    }
    value_type mult(const value_type & f, const value_type & g) const {
        return f * g;
    }
};

#line 2 "number/matrix_template.hpp"
#include <array>
#include <cstdint>
#line 2 "utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 5 "number/matrix_template.hpp"

template <typename T, std::size_t H, std::size_t W>
using matrix = std::array<std::array<T, W>, H>;

template <typename T, std::size_t A, std::size_t B, std::size_t C>
matrix<T, A, C> operator * (matrix<T, A, B> const & a, matrix<T, B, C> const & b) {
    matrix<T, A, C> c = {};
    REP (y, A) REP (z, B) REP (x, C) c[y][x] += a[y][z] * b[z][x];
    return c;
}
template <typename T, std::size_t H, std::size_t W>
std::array<T, H> operator * (matrix<T, H, W> const & a, std::array<T, W> const & b) {
    std::array<T, H> c = {};
    REP (y, H) REP (z, W) c[y] += a[y][z] * b[z];
    return c;
}

template <typename T, std::size_t H, std::size_t W>
matrix<T, H, W> operator + (matrix<T, H, W> const & a, matrix<T, H, W> const & b) {
    matrix<T, H, W> c;
    REP (y, H) REP (x, W) c[y][x] = a[y][x] + b[y][x];
    return c;
}

template <typename T, std::size_t N>
std::array<T, N> operator + (std::array<T, N> const & a, std::array<T, N> const & b) {
    std::array<T, N> c;
    REP (i, N) c[i] = a[i] + b[i];
    return c;
}

template <typename T, std::size_t H, std::size_t W>
matrix<T, H, W> zero_matrix() {
    return {};
}

template <typename T, std::size_t N>
matrix<T, N, N> unit_matrix() {
    matrix<T, N, N> a = {};
    REP (i, N) a[i][i] = 1;
    return a;
}

template <typename T, std::size_t N>
matrix<T, N, N> matpow(matrix<T, N, N> x, int64_t k) {
    matrix<T, N, N> y = unit_matrix<T, N>();
    for (; k; k >>= 1) {
        if (k & 1) y = y * x;
        x = x * x;
    }
    return y;
}
#line 3 "monoids/matrix_template.hpp"

template <class T, int N>
struct matrix_monoid {
    typedef matrix<T, N, N> value_type;
    value_type f;
    value_type unit() const {
        return unit_matrix<T, N>();
    }
    value_type mult(const value_type & f, const value_type & g) const {
        return f * g;
    }
};