number/matrix.hpp

• View this file on GitHub
• Last update: 2021-08-30 04:35:37+09:00
• Include: #include "number/matrix.hpp"

Depends on

• utils/macros.hpp

Verified with

• number/matrix.yukicoder-1073.test.cpp

Code

#pragma once
#include <cstdint>
#include <vector>
#include "../utils/macros.hpp"

template <typename T>
std::vector<std::vector<T> > operator * (const std::vector<std::vector<T> >& a, const std::vector<std::vector<T> >& b) {
    int n = a.size();
    std::vector<std::vector<T> > c(n, std::vector<T>(n));
    REP (y, n) {
        REP (z, n) {
            REP (x, n) {
                c[y][x] += a[y][z] * b[z][x];
            }
        }
    }
    return c;
}

template <typename T>
std::vector<T> operator * (const std::vector<std::vector<T> >& a, const std::vector<T>& b) {
    int n = a.size();
    std::vector<T> c(n);
    REP (y, n) {
        REP (z, n) {
            c[y] += a[y][z] * b[z];
        }
    }
    return c;
}

template <typename T>
std::vector<std::vector<T> > unit_matrix(int n) {
    auto e = std::vector<std::vector<T> >(n, std::vector<T>(n));
    REP (i, n) {
        e[i][i] = 1;
    }
    return e;
}

template <typename T>
std::vector<std::vector<T> > zero_matrix(int n) {
    return std::vector<std::vector<T> >(n, std::vector<T>(n));
}

template <typename T>
std::vector<std::vector<T> > matpow(std::vector<std::vector<T> > x, int64_t y) {
    int n = x.size();
    auto z = unit_matrix<T>(n);
    for (int64_t i = 1; i <= y; i <<= 1) {
        if (y & i) {
            z = z * x;
        }
        x = x * x;
    }
    return z;
}

#line 2 "number/matrix.hpp"
#include <cstdint>
#include <vector>
#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.hpp"

template <typename T>
std::vector<std::vector<T> > operator * (const std::vector<std::vector<T> >& a, const std::vector<std::vector<T> >& b) {
    int n = a.size();
    std::vector<std::vector<T> > c(n, std::vector<T>(n));
    REP (y, n) {
        REP (z, n) {
            REP (x, n) {
                c[y][x] += a[y][z] * b[z][x];
            }
        }
    }
    return c;
}

template <typename T>
std::vector<T> operator * (const std::vector<std::vector<T> >& a, const std::vector<T>& b) {
    int n = a.size();
    std::vector<T> c(n);
    REP (y, n) {
        REP (z, n) {
            c[y] += a[y][z] * b[z];
        }
    }
    return c;
}

template <typename T>
std::vector<std::vector<T> > unit_matrix(int n) {
    auto e = std::vector<std::vector<T> >(n, std::vector<T>(n));
    REP (i, n) {
        e[i][i] = 1;
    }
    return e;
}

template <typename T>
std::vector<std::vector<T> > zero_matrix(int n) {
    return std::vector<std::vector<T> >(n, std::vector<T>(n));
}

template <typename T>
std::vector<std::vector<T> > matpow(std::vector<std::vector<T> > x, int64_t y) {
    int n = x.size();
    auto z = unit_matrix<T>(n);
    for (int64_t i = 1; i <= y; i <<= 1) {
        if (y & i) {
            z = z * x;
        }
        x = x * x;
    }
    return z;
}

Back to top page