矩阵快速幂

矩阵快速幂

前置芝士

矩阵乘法

  • 当矩阵\(A\)的列数与矩阵\(B\)的行数相等时,矩阵\(A\)与矩阵\(B\)可进行相乘

  • 如矩阵\(A\)为\(m\times n\)的矩阵,矩阵\(B\)为\(n \times p\)的矩阵,他们的乘积\(C\)是一个\(m \times p\)的矩阵

  • \(C\)的第\(i\)行\(j\)列的元素为

    \[c_{i,j}=\sum\limits^n_{r=1}a_{i,r}b_{r,j} \]

  • 举例

    • \(\begin{bmatrix}a\\c\end{bmatrix} \times \begin{bmatrix}b&d\end{bmatrix}=\begin{bmatrix}a\times b&a \times d\\c \times b&c\times d\end{bmatrix}\)

    • 矩阵快速幂

      懒得打了直接引的百度百科图片

  • 方阵:行数等于列数的矩阵

  • 单位矩阵:左上角到右下角这条对角线上全为1、其余全为0的方阵88(相当于乘法中的1)

  • 矩阵乘法有结合律、分配律,没有交换律

快速幂

快速幂(主要用带取模的快速幂)

矩阵快速幂

  • 顾名思义,其实就是矩阵乘法+快速幂

  • 模板(伪)

  • //还没编译,大概能跑,看个思路
    
    struct Matrix{
    	int G[105][105];
    };
    
    int m,n,p,MOD;
    
    //生成单位矩阵 
    Matrix CI(Matrix &A){
    	for(int i = 0;i<n;i++){
    		for(int j = 0;j<n;j++){
    			A[i][j] = (i == j);
    		}
    	}
    }
    
    //矩阵乘法
    Matrix MatrixMul(Matrix A,Matrix B){
    	Martix R;
    	memset(R.G,0,sizeof(R.G));
    	for(int i = 0;i<m;i++){
    		for(int j = 0;j<n;j++){
    			for(int k = 0;k<n;k++){
    				R.G[i][k] += A.G[i][j]*B.G[j][k];
    				R.G[i][k] %= MOD;
    			}
    		}
    	}
    	return R;
    }
    //矩阵快速幂
    Matrix MatrixQuickPow(Matrix A,int b){
    	Matrix I,Result;
    	CI(I);
    	while(b){
    		if(b&1) Result = MatrixMul(Result,A);
    		A = MatrixMul(A,A);
    		b /= 2;
    	}
    	return Result;
    }
    

应用

  1. 超大数的递推,如P1962斐波那契数列

    因为我们知道,

    \(f(n)=f(n-1)+f(n-2)\)

    \(f(n-1)=f(n-1)\)

    \(\begin{align}\begin{cases}f(n)&=1\times f(n-1)+1\times f(n-2)\\f(n-1)&=1\times f(n-1)+0\times f(n-2)\end{cases}\end{align}\)

    因此我们得到了

    \(\begin{bmatrix}f(n)\\f(n-1)\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\times \begin{bmatrix}f(n-1)\\f(n-2)\end{bmatrix}\)

    因为矩阵乘法具有结合律,所以斐波那契数列的第n项为

    \(\begin{bmatrix}f(n)\\f(n-1)\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-2}\times \begin{bmatrix}1\\1\end{bmatrix}\)

    算就完了

    矩阵的katex打起来太麻烦了( ‵o′)

上一篇:[LeetCode] 977. Squares of a Sorted Array 有序数组的平方值


下一篇:2022-01-20 快速排序——热爱混乱,厌恶有序的排序方法