矩阵乘法
矩阵 ： 什么是矩阵
类似于这个就是矩阵，矩阵是 \(n \times m\) 的， \(n\) 为行数， \(m\) 为列数 。
为了方便，我们简化一下这个矩阵，没有对其进行一系列的限制。
矩阵加减法
显而易见 ，就是两个矩阵进行相加减呗，不过这个相加减得出来的，也是一个矩阵，这个矩阵也是一样的 ，我们假设 $A = n \times m , B = n \times m $ 为两个准备相加减的矩阵， \(C = n \times m\) 为加减后的结果矩阵， \(C\) 矩阵中的位置 \(i,j\) 就是 \(A\) 矩阵 \(i,j\) 和 \(B\) 矩阵 \(i,j\) 直接相加减的结果。
矩阵乘法
单位矩阵
一种特殊的矩阵，主对角线（从左上到右下角）是1，其余全部为0
也是两个矩阵的乘法
两个矩阵相乘，定义为 \(A = n\times m , B = k\times n\) ,由此可以看出，第一个矩阵的列数要等于第二个矩阵的行数才能进行相乘。 取出第一个矩阵的一行，\(\times\)第一个的矩阵的列数，得到结果矩阵
$ \begin{bmatrix} a1 & a2 \ a3 & a4 \ \end{bmatrix} $ \(\times\) $ \begin{bmatrix} b1 & b2 \ b3 & b4 \ \end{bmatrix} $ = $ \begin{bmatrix} a1\times b1 + a3 \times b3 & a1\times b2 + a3 \times b4\ a2 \times b1 + a4\times b3 & a2\times b2 + a4 \times b4 \ \end{bmatrix} $
我们假设结果矩阵为 \(C\) ,那么
\(C_{i,j} = \sum\limits_{k = 1}^{M}A_{i,k}\times B_{k,j}\)
其中 \(M\) 为 \(A\) 矩阵的行数，或者说是 \(B\) 矩阵的列数。 ，记忆一下即可。
同样的， 如果 \(A\) 矩阵为 \(N\times M\) 的矩阵 ， \(B\) 为 \(M\times K\) ,那么结果矩阵 \(C\) 也就是 \(N\times K\) 的矩阵。
矩阵乘法的性质 ：
具有结合律 即为 \(A \times (B \times C )= (A \times B )\times C\)
不具备交换律，即为 \(A \times B \not = B\times A\)
左分配律 ，为 \(A\times (B + C) = A\times C + B \times C\)
右分配律 ，为 \((A + B) \times C = A \times C + B\times C\)
模板：矩阵快速幂
【\(description\)】：
给定一个 \(n \times n\) 的矩阵 \(A\) , 计算 \(A^k\)
【\(solution\)】 :
也就是将快速幂中的数字换成了矩阵，其它保持一致。
【\(Code\)】:
枚举顺序与时间的关系 ：
例题 ： 斐波那契数列
【\(description\)】 :
假设 \(f_i\) 代表斐波那契数列的第 \(i\) 项 ，求解 \(f_n\) % \(p\) , 其中 \(n,p\leq 10^9\)
【\(solution\)】:
首先是显然的 \(O(n)\) 递推式 \(f_i = f_{i-1} + f_{i-2}\)。
但 \(10^9\) 显然是不可过的。 我们考虑一下是否可以用矩阵乘法加速递推 。
也就是我们需要得到
$ \begin{bmatrix} f_{i - 1} & f_{i - 2} \ \end{bmatrix} $ \(\times\) \(A\) 这一个矩阵， 是否可以得到一个关于 \(f_i\) 的 ，首先我们可以确定，得到的必然也是一个 \(1 \times 2\) 的一个矩阵，然后我们根据矩阵的性质，可以知道 ，\(A\) 矩阵应该是一个 \(2 \times 2\) 的矩阵。
我们假设为 $ \begin{bmatrix} a1 & a2 \ a3 & a4 \ \end{bmatrix} $ , 同样的，我们假设 \(f1 = f_{i-1} , f2 = f_{i-2}\) , 那么结果矩阵也就是
$ \begin{bmatrix} f1 \times a1 + f2 \times a3 & f1 \times a2 + f2 \times a4 \ \end{bmatrix} $
其中有一个必然是 \(f_{i}\) 的，也就是 \(f_{i-1 } + f_{i-2}\)
然后我们其中也必然会有个 \(f1\) , 来搞一下下次的运行，也就是 \(f_{i+1} = f_{i} + f_{i - 1}\) ,那么结果矩阵也就显而易见了，为
$ \begin{bmatrix} f_{i-1} & f_i \ \end{bmatrix} $
那么同样的，推导出 \(A=\)$ \begin{bmatrix} 0 & 1 \ 1 & 1 \ \end{bmatrix} \(
然后就是跑一个 矩阵快速幂就结束了。
【\)Code$】：
/*
by : Zmonarch
知识点 ：矩阵乘法 ，快速幂
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <cstring>
#include <map>
#include <cstdlib>
#define int long long
#define inf 2147483647
const int kmaxn = 1e6 + 10 ;
const int kmod = 1e9 + 7 ;
namespace base
{
inline int Min(int a , int b) { return a < b ? a : b ; } ;
inline int Max(int a , int b) { return a > b ? a : b ; } ;
inline int Abs(int a ) { return a < 0 ? - a : a ; } ;
};
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int n , p ;
struct matrix //用结构体存矩阵
{
int n , m ; // n * m 的矩阵
int a[3][3] ;
matrix()
{
n = m = 0 ;
std::memset(a , 0 , sizeof(a)) ;
}
} ;
matrix operator*(const matrix &m1 , const matrix &m2) //定义矩阵乘法法则
{
matrix m3 ; //结果矩阵
m3.n = m1.n ;
m3.m = m2.m ;
for(int i = 1 ; i <= m3.n ; i++) //结果矩阵的行数
{
for(int j = 1 ; j <= m3.m ; j++) //结果矩阵的列数
{
int sum = 0 ;
for(int k = 1 ; k <= m1.m ; k++) //进行相加
{
sum += (m1.a[i][k] * m2.a[k][j]) ;
sum = sum % kmod ;
}
m3.a[i][j] = sum % kmod ; //固定结果矩阵
}
}
return m3 ;
}
matrix m2 ;
matrix quick_pow( int n ) //定义矩阵快速幂
{
matrix a ; //单位矩阵
//a.m = a.n = 2 ;
a.a[1][1] = 1 ; a.a[1][2] = 0 ;
a.a[2][1] = 0 ; a.a[2][2] = 1 ;
m2.m = m2.n = 2 ;
m2.a[1][1] = 0 , m2.a[1][2] = 1 ;
m2.a[2][1] = 1 , m2.a[2][2] = 1 ;
while(n)
{
if(n & 1) a = a * m2 ;
m2 = m2 * m2 ;
n >>= 1 ;
}
return a ;
}
signed main()
{
n = read() ; //, p = read() ;
if(n <= 2)
{
printf("1") ;
return 0 ;
}
matrix m1 ;
m1.n = 1 , m1.m = 2 ;
m1.a[1][1] = 1 , m1.a[1][2] = 1 ;
m1 = m1 * quick_pow( n - 2 ) ;
printf("%lld\n" , m1.a[1][2] % kmod) ;
return 0 ;
}