src/math/matpow.hpp

View this file on GitHub
Last update: 2026-01-30 22:16:29+09:00
Include: #include "src/math/matpow.hpp"

Depends on

src/template.hpp

Code

#include "../template.hpp"

template <class T>
vector<vector<T>> mat_mul(vector<vector<T>> a,vector<vector<T>> b){
    vector ret(si(a),vector<T>(si(b[0])));
    rep(i,si(a)){
        rep(j,si(b[0])){
            rep(k,si(b)){
                ret[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
    return ret;
}

template <class T>
vector<vector<T>> mat_pow(vector<vector<T>> a,long k){
    vector ret(si(a),vector<T>(si(a)));
    rep(i,si(a)) ret[i][i]=1;
    while(k>0){
        if(k&1) ret=mat_mul(a,ret);
        a=mat_mul(a,a);
        k>>=1;
    }
    return ret;
}

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 2 "src/math/matpow.hpp"

template <class T>
vector<vector<T>> mat_mul(vector<vector<T>> a,vector<vector<T>> b){
    vector ret(si(a),vector<T>(si(b[0])));
    rep(i,si(a)){
        rep(j,si(b[0])){
            rep(k,si(b)){
                ret[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
    return ret;
}

template <class T>
vector<vector<T>> mat_pow(vector<vector<T>> a,long k){
    vector ret(si(a),vector<T>(si(a)));
    rep(i,si(a)) ret[i][i]=1;
    while(k>0){
        if(k&1) ret=mat_mul(a,ret);
        a=mat_mul(a,a);
        k>>=1;
    }
    return ret;
}