矩阵乘法、矩阵快速幂

矩阵

就是一个矩阵，嗯。

\[\begin{bmatrix} 1 & 1\\ 4 & 5\\ 1 & 4 \end{bmatrix} \]

发明出来据说是为了偷懒。

矩阵乘法

不是传统意义上的相乘，只要矩阵 \(A\) 的列数等于矩阵 \(B\) 的行数，就可以做矩阵乘法。

举一个简单的例子：

\[A= \begin{bmatrix} 1&2&3\\ 3&1&4\\ 2&2&1 \end{bmatrix} \]

\[B= \begin{bmatrix} 5&6&3\\ 2&7&9\\ 8&4&5 \end{bmatrix} \]

\[A\times B= \begin{bmatrix} 1\times5+2\times2+3\times8 & 1\times6+2\times7+3\times4 & 1\times3+2\times9+3\times5\\ 3\times5+1\times2+4\times8 & 3\times6+1\times7+4\times4 & 3\times3+1\times9+4\times5\\ 2\times5+2\times2+1\times8 & 2\times6+2\times7+1\times4 & 2\times3+2\times9+1\times5 \end{bmatrix} \]

上面三个矩阵 \(L^AT_EX\) 打了12min。。。

发现了吗？矩阵的乘积的第 \(i\) 行 \(j\) 列上的数，就是第一个矩阵的第 \(i\) 行乘上第二个矩阵的第 \(j\) 列的和。

矩阵中的 "1"：\(\begin{bmatrix} 1&0\\ 0&1 \end{bmatrix}\)

这种对角线全是 \(1\) 的矩阵，任意矩阵乘上它不会变。

矩阵乘法不满足交换律，满足结合律。

\(\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}\times\begin{bmatrix} 11&4\\ 5&14 \end{bmatrix}\neq\begin{bmatrix} 11&4\\ 5&14 \end{bmatrix}\times\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}\)

矩阵快速幂

由于矩阵乘法满足结合律，所以对于矩阵 \(M^k\)，可以拆分成 \(M^{2^1}\times M^{2^2}\times...\times M^{2^l}\) 的形式，也就是快速幂。

代码用封装 + 重载乘法实现。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
struct TVO{int c[105][105];
}A,B;
int n,k;
TVO operator*(const TVO &x,const TVO &y) {TVO a;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a.c[i][j]=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){a.c[i][j]=(a.c[i][j]+x.c[i][k]*y.c[k][j]+mod)%mod;}}}return a;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>A.c[i][j];for(int i=1;i<=n;i++) B.c[i][i]=1;while(k>0){if(k%2==1) B=B*A;A=A*A,k>>=1;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<B.c[i][j]<<" ";cout<<"\n";}return 0;
}

嗯呐。

矩阵快速幂优化递推

看经典的斐波那契数列：

\[f_n=f_{n-1}+f_{n-2} \]

我们用一个矩阵 \(\begin{bmatrix}f_{n}&f_{n-1}\end{bmatrix}\) 记录斐波那契数列。

想要求出这个矩阵，我们需要知道 \(\begin{bmatrix}f_{n-1}&f_{n-2}\end{bmatrix}\)

假设我们知道 \(\begin{bmatrix}f_{n-1}&f_{n-2}\end{bmatrix}\) 时。

目标求出 \(f_n\)，需要 \(f_{n-1}\)、\(f_{n-2}\)，矩阵的第一列就是 \(1,1\)

目标求出 \(f_n-1\)，需要 \(f_{n-1}\)，矩阵的第二列就是 \(0,1\)

所以设矩阵 \(M=\begin{bmatrix}0&1\\1&1\end{bmatrix}\)，答案矩阵 = \(\begin{bmatrix}1&1\end{bmatrix}\times M^n\)。

\(M^n\) 可以容矩阵快速幂解决。