矩阵乘法

OI 中的主要应用在于加速计算线性递推式。

举例来自 OI-wiki。

通常使用二维数组模拟矩阵。

矩阵乘法的一个前提是两个矩阵中存在一个的行数等于另一个的列数的情况，因此在处理非正方形时的矩阵乘法时要注意循环顺序对应的行与列。

通常将二维数组封到一个结构体内，定义如下：

struct Matrix
{
	int a[x][y];
	// 表示矩阵的行数和列数
	Matrix(){memset(a,0,sizeof a);}
	// 初始化
}

个人不是很喜欢将行列放到和数组一起，不方便转移，看个人习惯。

乘法：

Matrix mul(Matrix a,Matrix b,int x,int y,int z)
{
	// 使目标矩阵规格与 a 矩阵相同
	// 设 a 的行数等于 b 的列数
	// x 为目标矩阵的列数，z 为 b 矩阵的行数，y 为二者相同的那一值
	Matrix c;
	for(int i=0;i<x;i++)
		for(int j=0;j<z;j++)
			for(int k=0;k<y;k++)
				c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod+mod)%mod;
	return c;

}

快速幂：通常情况下仅会出现方阵的快速幂。

Matrix pow(rmm a,int t,int x)
{
	Matrix b;
	for(int i=0;i<x;i++) b.a[i][i]=1;
	// 构造一个单位矩阵
	while(t)
	{
		if(t&1) b=mul(a,b,x,x,x);
		a=mul(a,a,x,x,x);
		t>>=1;
	}
	return b;
}

应用上：当你遇到一个线性复杂度明显过不去但确定是正解的时候，可以尝试使用矩阵加速。

推矩阵上：一般考虑将结果和与推出结果有关的变量放入矩阵，根据代数式找到其对应的 base 矩阵（通常为方阵），然后找到初始矩阵的值后，快速幂即可。

例题：

• 佳佳的Fibonacci

很好且基础的一道题，建议自己推一推，做完能更好地体会到矩阵的神奇。

Fibonacci 是个很众所周知的递推数列，所以构造矩阵的方法也很多，记得当时刚奥赛合班推了一个下午，挺有成就感的。

• 崩坏星穹铁道
  别骂了知道这道题很唐

题意很简单，没玩过的崩铁的也比较好理解，反倒是牢玩家容易想复杂。

挂一篇我的题解。

递推式极易得出，但 \(10^18\) 的范围显然不是简单线性能过的，所以这道题就是一个隐晦的矩阵快速幂基础题。

• GT考试

建议先学完 kmp 再做，不然抄板子过会损失很多乐趣。

挂一篇我的题解（魔怔人别太在意变量名）。

一道典型的矩阵加速的题，递推式想出来后，把矩阵迁移到题目中就好。

完结撒花~

祝学好每一个新（老）算法~