矩阵乘法，顾名思义矩阵与矩阵相乘，
两矩阵可相乘的前提：第一个矩阵的行与第二个矩阵的列相等
相乘原则：
a b * A B = a*A+b*C a*c+b*D
c d C D = c*A+d*C c*A+d*C
上代码
struct matrix
{
ll a[maxn][maxn];
};
matrix matrix_mul(matrix x,matrix y)
{
matrix temp;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
temp.a[i][j]=;
for(int k=;k<=n;k++)
{
temp.a[i][j]+=(x.a[i][k]*y.a[k][j])%mod;
temp.a[i][j]%=mod;
}
}
return temp;
}
∵矩阵乘法满足结合律（不满足交换律）
∴可用快速幂
矩阵快速幂与一般快速幂极其相似，只是把两个数相乘改成了两个矩阵相乘（用个相乘函数即可），所以完全可以按照快速幂的写法来写；
matrix matrix_pow(matrix a,ll b)
{
matrix v;
for(int i=;i<=n;i++) v.a[i][i]=; //初始化，就和把数字初始化成 1 一样，矩阵这样初始化
while(b>)
{
if(b&) v=matrix_mul(v,a);
a=matrix_mul(a,a);
b=b>>;
}
return v;
}
※矩阵快速幂解决线性递推式
举个栗子（我有一盆栗子随便举） 斐波那契序列 （F[n]=F[n-1]+F[n-2]）
很多童鞋知道矩阵快速幂可解决斐波那契序列,但并不知道原因
事实上矩阵快速幂可以解决绝大多数线性递推式（不敢说所有=-=，万一呢）
对于斐波那契，递推矩阵（自己起的=-=）为
1 1
0 1
具体推导初始矩阵过程如下（方法不唯一）：（以斐波那契额为例）
我们要做的是使F[n-1]+F[n-2]乘某个矩阵得出第一项为F[n]（个人理解的=-=）
则 F[n] = a b * F[n-1]
F[n-1] c d F[n-2]
∵F[n]=F[n-1]+F[n-2]
则可得 F[n-1]+F[n-2] = a b * F[n-1]
F[n-1] c d F[n-2]
设F[n-1]为A,F[n-2]为B
则为 A+B = a b * A = a*A+b*B （将右边矩阵乘开了）
B c d * B c*A+d*B
则可以看到 a*A+b*B=A+B
c*A+d*B=B
很容易看出a=1,b=1,c=0,d=1
所以递推矩阵为
1 1
0 1
普通斐波那契F[1]=1，F[2]=1;
那为什么可以用矩阵快速幂呢？
设上边的0,1为A，斐波那契初始矩阵为B，当N》=2的时候我们可以求斐波那契
比如斐波那契的3项就应该是
A*A*B即可（因为N大于等于2所以要把求得项数减去1然后再乘）
类似的我们可以求斐波那契的第N项
即A*A*A*......*A*B一共乘N-1项。
这个时候我们发现都是乘法耶~那我们就快速幂把，好~快速幂所以我们就完成了快速幂。
所以每一n-1幂所对应的F[n]就是答案，
但F[1]与F[2]为其他数呢，就不能只是这样做了
∵矩阵乘法满足交换律
∴现将递推矩阵进行n次幂运算
再使其乘 F[1] 矩阵，即可得出答案=-=
F[2]