icpc/matrix.hpp

• View this file on GitHub
• Last update: 2023-05-31 02:53:46+09:00
• Include: #include "icpc/matrix.hpp"
• Link: https://onlinejudge.u-aizu.ac.jp/problems/3332

Depends on

• icpc/template.hpp

Code

#pragma once

#include "icpc/template.hpp"

// https://onlinejudge.u-aizu.ac.jp/problems/3332

constexpr ll MOD = 998244353;

using Mat = V<V<ll>>;
Mat mul(Mat& a, Mat& b) {
    int N = int(a.size());
    Mat c(N, V<ll>(N));
    REP(i, N) REP(k, N) REP(j, N) c[i][j] = (c[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
    return c;
}

Mat pow(Mat& a, ll k) {
    int N = int(a.size());
    Mat res(N, V<ll>(N));
    REP(i, N) res[i][i] = 1;
    while (k) {
        if (k & 1) res = mul(res, a);
        a = mul(a, a);
        k >>= 1;
    }
    return res;
}

#line 2 "icpc/matrix.hpp"

#line 2 "icpc/template.hpp"

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;
template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[ ";
    for (auto& vi : v) os << vi << ", ";
    return os << "]";
}

#ifdef LOCAL
#define show(x) cerr << __LINE__ << " : " << #x << " = " << x << endl;
#else
#define show(x) true
#endif

using uint = unsigned int;
using ull = unsigned long long;

// g++ -g -fsanitize=undefined,address -DLOCAL -std=gnu++17
#line 4 "icpc/matrix.hpp"

// https://onlinejudge.u-aizu.ac.jp/problems/3332

constexpr ll MOD = 998244353;

using Mat = V<V<ll>>;
Mat mul(Mat& a, Mat& b) {
    int N = int(a.size());
    Mat c(N, V<ll>(N));
    REP(i, N) REP(k, N) REP(j, N) c[i][j] = (c[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
    return c;
}

Mat pow(Mat& a, ll k) {
    int N = int(a.size());
    Mat res(N, V<ll>(N));
    REP(i, N) res[i][i] = 1;
    while (k) {
        if (k & 1) res = mul(res, a);
        a = mul(a, a);
        k >>= 1;
    }
    return res;
}

Back to top page