矩阵法

前言

• 自我感觉矩阵法在优化动态规划时的实质就是在转移上的优化；

• 对于转移数量多且重复的操作可以打包进行加速。

• 在构造矩阵时想好矩阵每一位的值的意义和总转移次数。

• 别固向思维，矩阵快速幂可以进行多次，不一定只矩阵快速幂一次。

前置知识

• 1.矩阵乘法

• 2.快速幂（此处不讲）

---

矩阵

简单介绍

矩阵可以看成一个 $n\times m$ 的二维数组，举个例子：

$\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$

这就是个 $3\times 3$ 的（单位）矩阵。

【单位矩阵】

单位矩阵的性质就是任意一个矩阵合法乘以一个单位矩阵，不改变矩阵的值，其作用相当于整数 $1$。

---

矩阵加速的应用

• ① 线性递推

• ② 动态规划优化

• ③ 图论

---

讲解的定义

接下来的讲解会用到两个矩阵 $A$ 和 $B$。

现在定义 $n_A$ 是 $A$ 矩阵的行个数，$m_A$ 是 $A$ 矩阵的列个数;

$n_B$ 是 $B$ 矩阵的行个数，$m_B$ 是 $B$ 矩阵的列个数。

矩阵加法

【前提】

相加的两个矩阵 $A$ 和 $B$ 必须满足 $n_A=n_B$ 且 $m_A=m_B$。

【加法原则】

然后就是基本的对位相加，不多作解释。

矩阵乘法

【前提】

相加的两个矩阵 $A$ 和 $B$ 必须满足 $m_A=n_B$。

【乘法原则】

小技巧：记住 $A$ 的第 $i$ 行乘以 $B$ 的第 $j$ 列，也就是 $A_{i,k}\times B_{k,j}$；得到到 $C$ 的第 $i$ 行第 $j$ 列的值，即 $C_{i,j}$。

这里的乘法我们需要用到重载运算符，代码如下：

inline Matrix operator * (const Matrix &A,const Matrix &B) {
	Matrix C;
	int Ax,Ay,Bx,By;
	Ax=n,Ay=Bx=n,By=n;
	for(int i=1;i<=Ax;i++) {
		for(int j=1;j<=By;j++) {
			for(int k=1;k<=Ay;k++)
				C.dat[i][j]=(C.dat[i][j]+(A.dat[i][k]%mod)*(B.dat[k][j]%mod)%mod)%mod;
		}
	}
	return C;
}

举个小栗子：

转移方程是 $f_i=f_{i-1}+f_{i-2}+1$；

那么从 $i$ 转移到 $i+1$ 时，

矩阵 $A$：

$\left[\begin{array}{ccc}1& 1& 1\\ 1& 0& 0\\ 0& 0& 1\end{array}\right]$

矩阵 $B$：

$\left[\begin{array}{c}{f}_{i-1}\\ f_{i-2}\\ 1\end{array}\right]$

那么矩阵 $C$ 就为

$\left[\begin{array}{c}{f}_i\\ f_{i-1}\\ 1\end{array}\right]$

再把矩阵 $C$ 赋予给 $A$，到了 $i+1$ 时，

矩阵 $A$ 就为

$\left[\begin{array}{c}{f}_{(i+1)-1}\\ f_{(i+1)-2}\\ 1\end{array}\right]$

即对于 $j=i+1$ 时的

$\left[\begin{array}{c}{f}_{j-1}\\ f_{j-2}\\ 1\end{array}\right]$

这里如果我们需要求出 $f_n$，我们需要将 $i$ 转移到第 $n+1$，矩阵 $A,B$ 和程序总转移次数是根据不同题目的性质而改变的。

在构造矩阵做草稿的时候可以把 $A$ 和 $B$ 放在一起看，运用空间想象（也可以画出来）判断得出的矩阵 $C$ 的每一位是否符合预想的要求。

满足的【乘法运算】

矩阵乘法满足乘法结合律，乘法分配律；

但不满足乘法交换律！！！

---

矩阵快速幂

struct Matrix {
	unsigned long long dat[N][N];
	Matrix() {
		for(int i=1;i<N;i++) {
			for(int j=1;j<N;j++)
				dat[i][j]=0;
		}
	}
	inline void build() {
		for(int i=1;i<=3;i++)
			dat[i][i]=1;
		return ;
	}
};
inline Matrix operator * (const Matrix &A,const Matrix &B) {
	Matrix C;
	int Ax,Ay,Bx,By;
	Ax=3,Ay=Bx=3,By=3;
	for(int i=1;i<=Ax;i++) {
		for(int j=1;j<=By;j++) {
			for(int k=1;k<=Ay;k++) 
				C.dat[i][j]=(C.dat[i][j]+(A.dat[i][k]%m)*(B.dat[k][j]%m)%m)%m; 
		}
	}
	return C;
}
inline Matrix Mqpow(Matrix a,int p) {
	Matrix res;
	res.build();
	while(p) {
		if(p&1)
			res=res*a;
		a=a*a,p>>=1;
	}
	return res;
}

---

关于常数优化

小技巧：在不改变答案贡献的前提下改变状态转移，以保证内存访问是连续的。

解释

简单讲讲，就假设现在有转移方程为 $f_{i,j}+=f_{i-1,j}$，我们在转移时内存上为了找到 $f_{i-1,j}$，至少要往前访问一行；

那改一改转移式子为 $f_{i,j}+=f_{i,j-1}$（这里不讲究两个转移式的互相正确性先），转移时内存只需要向前找一位，做到内存访问上的优化。

矩阵乘法上的应用

这里矩阵乘法时将 $i,j,k$ 的顺序改成 $i,k,j$ 的顺序循环，这样能保证数组的内存访问是连续的。

【理由】

$A_{i,k}$ 的访问地址不变，而 $B_{k,j}$ 和 $C_{i,j}$ 仅是往下一个地址走，比原来的跳着访问地址显然可以起到一定的优化。