1.矩陣乘法

設矩陣有 \(H\) 行，\(L\) 列，則兩個矩陣 \(MatA,MatB\) 進行乘法，需要滿足 \(MatA.L=MatB.H\)。則結果矩陣 \(MatR_{i,j}=\sum\limits^{n}_{z=1}MatA_{i,z}*MatB_{z,j}\)。

性質： 結合律，但不滿足交換律。

mat operator *(mat a,mat b)
{
	mat c;
	memset(c.mat,0,sizeof(c.mat));
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int z=1;z<=n;z++)
			{
				c.mat[i][z]+=a.mat[i][k]*b.mat[k][z]%mod;
				c.mat[i][z]%=mod;
			}
		}
	}
	return c;
}

2.矩陣快速冪

由于結合律，我們可以使用類似一般快速冪的方法快速計算 \(Mat^k\)。

值得注意的是，初始矩陣要滿足 \(MatR_{i,i}=1\)。

mat operator ^(mat a,int b)
{
	mat c;
	memset(c.mat,0,sizeof(c.mat));
	for(int i=1;i<=n;i++)
	{
		c.mat[i][i]=1;
	}
	while(b)
	{
		if(b&1)
		{
			c=c*a;
		}
		a=a*a;
		b>>=1;
	}
	return c;
}

3.用處

用于加速遞推。下面是斐波那契數列的推導：