矩阵学习笔记

标签：begin Matrix res 矩阵 笔记 times 学习 bmatrix

矩阵引入

矩阵引入来源于简洁表示线性方程组

例如：

\[\begin{cases} 2x+5y=10 \\ 4x+9y=39 \end{cases}\]

可以表示为：

\[\begin{bmatrix} 2 & 5 \\ 4 & 9 \end{bmatrix} \times \begin{bmatrix} x\\ y \end{bmatrix}\]

矩阵乘法

定义矩阵 \(A\) 为 \(n \times m\) 的矩阵，\(B\) 为 \(m \times q\) 的矩阵，且有矩阵 \(C\) 满足 \(C=A \times B\)，则

\[C_{i,j}=\sum_{k=1}^{m}A_{i,k} B_{k,j} \]

矩阵快速幂

\(O(\log n)\) 求矩阵 \(A\) 的 \(A^n\)。

矩阵快速幂 \(=\) 矩阵乘法 \(+\) 快速幂

重点在封装结构体，注意一些细节。

struct Matrix{
	ll a[120][120];//有时也要维护行和列
   Matrix(){
     memset(a,0,sizeof(a));//清空！！
   }
	inline Matrix operator*(const Matrix &T) const{
		Matrix res;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				for(int k=1;k<=n;k++){
             		//数据过大时，使用快速乘
					res.a[i][k]+=a[i][j]*(T.a[j][k])%mod;//是+=！！
					res.a[i][k]%=mod;
				}
			}
		}
		return res;
	}
}x;
inline Matrix Mat_ksm(Matrix y,ll k){
	Matrix res;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			res.a[i][j]=y.a[i][j]%mod;
		}
	}
	k--;
	while(k>0){
		if(k&1) res=res*y;
		y=y*y;
		k=k>>1;
	}
	return res;
}

矩阵加速递推

使用矩阵快速幂，将 \(O(n)\) 的时间复杂度优化至 \(O(\log n)\)。

类似动态规划的状态转移，明确转移前后矩阵，根据递推式推出后矩阵用前矩阵表示的各个系数，再构造矩阵存下系数，对着构造的矩阵做快速幂，最后乘上初始矩阵。

重点是构造转移矩阵。

例如：P1707 刷题比赛
复杂的构造矩阵

P4910 帕秋莉的手环
矩阵优化 \(dp\)

标签：begin,Matrix,res,矩阵,笔记,times,学习,bmatrix
From： https://www.cnblogs.com/dayz-break/p/18339797