学习笔记：矩阵快速幂

lizhous · 2022-10-11 20:28:42 · 个人记录

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.用处

用于加速递推。下面是斐波那契数列的推导：