矩阵乘法

给你两个大小分别为 \((n,k),(k,m)\) 的矩阵$$，相乘得到 \(n,m\) 大小的矩阵 \(C_{i,j}=\sum\limits_{i=1}^{m} A_{i,k}*B_{k*j}\)

矩阵乘法没有交换律，有结合律和分配律

方阵

大小为 \(n,n\) 的矩阵。特点是可以自己乘自己。

其中主对角线为 \(1\) 的矩阵我们称作单位矩阵(\(E\))，那么有\(A*E=A\)

例如

\[\left[\begin{matrix}1&0&0\\0&1&0\\0&0&1\end{matrix}\right] \]

矩阵快速幂

因为有矩阵快速幂，所以我们可以像整数一样进行快速幂

例题P3390

#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int MAXN = 105;
int n;
struct Matrix {
	int m[MAXN][MAXN];
	Matrix() {
		memset(m, 0, sizeof(m));
	}
};
Matrix multi(Matrix x, Matrix y) {
	Matrix res;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int t=1;t<=n;t++)
				res.m[i][j]=(res.m[i][j]+x.m[i][t]*y.m[t][j]%mod)%mod;
	return res;
}
Matrix quick_pow_matrix(Matrix a, int pw) {
	Matrix ans;
	for(int i=1;i<=n;i++)
		ans.m[i][i]=1;
	while(pw) {
		if(pw&1)ans=multi(ans, a);
		a=multi(a,a);
		pw>>=1;
	}
	return ans;
}
signed main() {
	int k;
	Matrix a;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a.m[i][j];
	Matrix ans=quick_pow_matrix(a,k);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++)
			printf("%lld ",ans.m[i][j]);
		printf("\n");
	}
	return 0;
}

矩阵加速递推

斐波那契数列

定义 \(fib_1=fib_2=1,fib_n=fib_{n-1}+fib_{n-2}(n\geq 3)\)

我们考虑用矩阵快速幂

\[\left[\begin{matrix} fib_{i-1}&fib_{i-2} \end{matrix}\right] \times \left[\begin{matrix} a&b\\c&d \end{matrix}\right] = \left[\begin{matrix} fib_i&fib_{i-1} \end{matrix}\right] \]

所以我们有

\[\begin{cases}fib_i=a*fib_{i-1}+c*fib_{i-2}\\fib_{i-1}=b*fib_{i-1}+d*fib_{i-2} \end{cases} \]

可以推出

\[\left[\begin{matrix} fib_{i-1}&fib_{i-2} \end{matrix}\right] \times \left[\begin{matrix} 1&1\\1&0 \end{matrix}\right] = \left[\begin{matrix} fib_i&fib_{i-1} \end{matrix}\right] \]