This documentation is automatically generated by online-judge-tools/verification-helper
#include "math/matrix.hpp"#pragma once
using i64 = long long;
constexpr i64 P = 998244353;
constexpr int mmax = 2000;
template<typename T>
struct matrix
{
int row, col;
i64 m[mmax][mmax];
matrix(int r, int c): row(r), col(c) {memset(m, 0, sizeof(m));}
matrix(int r, int c, int val): row(r), col(c)
{
memset(m, 0, sizeof(m));
for(int i = 1;i <= row;i++)
for(int j = 1;j <= col;j++)
m[i][j] = val;
}
matrix(int r, int c, std::vector<std::vector<T>> _m): row(r), col(c)
{
memset(m, 0, sizeof(m));
for(int i = 1;i <= row;i++)
for(int j = 1;j <= col;j++)
m[i][j] = _m[i][j];
}
matrix operator *= (const matrix &rhs)
{
assert(col == rhs.row);
i64 tmp[mmax][mmax];
memset(tmp, 0, sizeof(tmp));
for(int k = 1;k <= col;k++)
for(int i = 1;i <= row;i++)
for(int j = 1;j <= rhs.col;j++)
tmp[i][j] = (tmp[i][j] + ((m[i][k] * rhs.m[k][j]))) % P;
memcpy(m, tmp, sizeof(tmp));
return *this;
}
friend matrix operator *(const matrix &lhs, const matrix &rhs)
{
assert(lhs.col == rhs.row);
matrix res = lhs;
res *= rhs;
return res;
}
matrix<T> pow(T k)
{
assert(row == col);
k--;
matrix<T> Ans = *this, f = *this;
while(k)
{
if(k & 1)
Ans *= f;
f *= f;
k >>= 1;
}
return Ans;
}
};#line 2 "math/matrix.hpp"
using i64 = long long;
constexpr i64 P = 998244353;
constexpr int mmax = 2000;
template<typename T>
struct matrix
{
int row, col;
i64 m[mmax][mmax];
matrix(int r, int c): row(r), col(c) {memset(m, 0, sizeof(m));}
matrix(int r, int c, int val): row(r), col(c)
{
memset(m, 0, sizeof(m));
for(int i = 1;i <= row;i++)
for(int j = 1;j <= col;j++)
m[i][j] = val;
}
matrix(int r, int c, std::vector<std::vector<T>> _m): row(r), col(c)
{
memset(m, 0, sizeof(m));
for(int i = 1;i <= row;i++)
for(int j = 1;j <= col;j++)
m[i][j] = _m[i][j];
}
matrix operator *= (const matrix &rhs)
{
assert(col == rhs.row);
i64 tmp[mmax][mmax];
memset(tmp, 0, sizeof(tmp));
for(int k = 1;k <= col;k++)
for(int i = 1;i <= row;i++)
for(int j = 1;j <= rhs.col;j++)
tmp[i][j] = (tmp[i][j] + ((m[i][k] * rhs.m[k][j]))) % P;
memcpy(m, tmp, sizeof(tmp));
return *this;
}
friend matrix operator *(const matrix &lhs, const matrix &rhs)
{
assert(lhs.col == rhs.row);
matrix res = lhs;
res *= rhs;
return res;
}
matrix<T> pow(T k)
{
assert(row == col);
k--;
matrix<T> Ans = *this, f = *this;
while(k)
{
if(k & 1)
Ans *= f;
f *= f;
k >>= 1;
}
return Ans;
}
};