矩阵乘法

给你两个大小分别为 \((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
#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]
\]