struct Matrix {
ll mat[N][N];
};
// a: n*n b: n*n
Matrix mul_matrix(Matrix a, Matrix b, int n, ll m) {
Matrix res;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
res.mat[i][j] = 0;
for (int k = 0; k < n; k++) {
res.mat[i][j] += a.mat[i][k] * b.mat[k][j] % m;
res.mat[i][j] %= m;
}
}
}
return res;
}
// a^p
Matrix pow_matrix(Matrix a, ll p, int n, ll m) {
Matrix res;
// 单位矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
res.mat[i][j] = (i == j ? 1 : 0);
}
}
while (p != 0) {
if (p & 1)
res = mul_matrix(a, res, n, m);
a = mul_matrix(a, a, n, m);
p >>= 1;
}
return res;
}
大矩阵作为函数参数且以值传递会发生段错误。
一种大矩阵不会段错误的实现方式。
使用方式$c=A^nb \Rightarrow c^T=b^T(A^T)^n$
#define N 505
#define MOD 998244353
struct Matrix {
int mat[N][N];
int n;
Matrix(int n) : n(n) { memset(mat, 0, sizeof(mat)); }
inline void operator*=(const Matrix& o) {
int ans[n][n] = {};
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (mat[i][j])
for (int k = 0; k < n; k++)
ans[i][k] =
(ans[i][k] + (long long)(mat[i][j]) * o.mat[j][k]) %
MOD;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
mat[i][j] = ans[i][j];
}
void print() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << mat[i][j] << " ";
}
cout << "\\n";
}
}
};
void cpt(Matrix& a, Matrix& b, int n) {
// a *= b^n
for (; n; n >>= 1, b *= b)
if (n & 1)
a *= b;
// a.print();
}
/*
// a *= b^n
for (; n; n >>= 1, b *= b)
if (n & 1)
a *= b;
a.print();
*/
常系数的递推式
已知$f_0, f_1,\cdots,f_{k-1}$
$f_i= c_0+c_1f_{i-1}+c_2f_{i-2}+\cdots+c_kf_{i-k}, i\ge k$
构造$k+1$阶方阵转移
$\left[ \begin{array}{c} f_i \\\\ f_{i-1} \\\\ f_{i-2} \\\\ \vdots \\\\ f_{i-(k-2)} \\\\ f_{i-(k-1)} \\\\ 1 \end{array}\right] = \left[ \begin{array}{cccccc} c_1 & c2 & c3 & \cdots & c_{k-1} & c_k & c_0 \\\\ 1 & 0 & 0 & \cdots & 0 & 0 & 0 \\\\ 0 & 1 & 0 & \cdots & 0 & 0 & 0 \\\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\\\ 0 & 0 & 0 & \cdots & 0 & 0 & 0 \\\\ 0 & 0 & 0 & \cdots & 1 & 0 & 0 \\\\ 0 & 0 & 0 & \cdots & 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{c} f_{i-1} \\\\ f_{i-2} \\\\ f_{i-3} \\\\ \vdots \\\\ f_{i-(k-1)} \\\\ f_{i-k} \\\\ 1 \end{array}\right]$
二维状态转移只依赖前一维度
$f_{p,i} = \sum \limits_{j=0}^{n-1}f_{p-1, j}*c_{i,j}$
设置一个$n\times n$的转移矩阵A。设置元素$A_{i,j}$为前一状态$f_{p-1,i}$向当前状态$f_{p,j}$转移的贡献$c_{i,j}$
$\left[ \begin{array}{c} f_{p, 0} \\\\ f_{p, 1} \\\\ \vdots \\\\ f_{p, n-2} \\\\ f_{p, n-1} \end{array}\right] = \left[ \begin{array}{cccccc} c_{0,0} & c_{0,1} & \cdots & c_{0, n-2} & c_{0, n-1} \\\\ c_{1,0} & c_{1,1} & \cdots & c_{1, n-2} & c_{1, n-1} \\\\ \vdots & \vdots & \ddots & \vdots & \vdots \\\\ c_{n-2,0} & c_{n-2,1} & \cdots & c_{n-2, n-2} & c_{n-2, n-1} \\\\ c_{n-1,0} & c_{n-1,1} & \cdots & c_{n-1, n-2} & c_{n-1, n-1} \end{array} \right] \left[ \begin{array}{c} f_{p-1, 0} \\\\ f_{p-1, 1} \\\\ \vdots \\\\ f_{p-1, n-2} \\\\ f_{p-1, n-1} \end{array}\right]$