矩阵学习笔记1 矩阵乘法 快速幂【矩阵】

点击量：160

   矩阵是线性代数的内容，矩阵乘法和一般的乘法不同，矩阵A×B时要求A的列数=B的行数=k。算术结果：若$ C=A\times B,C_{xy}=\sum\limits _{i=1}^kA_{xi}\times B_{iy}$。

   因此我们有

$ \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \times  \begin{bmatrix} b_{11} &b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \\ b_{31} & b_{32} & b_{33} \end{bmatrix}$

$ =\begin{bmatrix} a_{11}\times b_{11}+a_{12}\times b_{21}+a_{13}\times b_{31} &a_{11}\times b_{12}+a_{12}\times b_{22}+a_{13}\times b_{32} & a_{11}\times b_{13}+a_{12}\times b_{23}+a_{13}\times b_{33} \\ a_{21}\times b_{11}+a_{22}\times b_{21}+a_{23}\times b_{31} & a_{21}\times b_{12}+a_{22}\times b_{22}+a_{23}\times b_{32} & a_{21}\times b_{13}+a_{22}\times b_{23}+a_{23}\times b_{33} \\ a_{31}\times b_{11}+a_{32}\times b_{21}+a_{33}\times b_{31} & a_{31}\times b_{12}+a_{32}\times b_{22}+a_{33}\times b_{32} & a_{31}\times b_{13}+a_{32}\times b_{23}+a_{33}\times b_{33} \end{bmatrix}$

    代码实现过程：

matrix cross(matrix a,matrix b)
{
    matrix m;
    m.x=a.x;
    m.y=b.y;
    for(int i=1;i<=a.x;i++)//a.y==b.x
        for(int j=1;j<=b.y;j++)
            for(int k=1;k<=a.y;k++)
            {
                m.a[i][j]+=a.a[i][k]*b.a[k][j];
                m.a[i][j]%=p;
            }
    return m;
}

   因为矩阵乘法基于代数乘法，所以代数的快速幂也适用于矩阵的快速幂，这种快速幂直接模拟即可。矩阵快速幂模板题

Code：（快速幂包括平方 乘法）

#include<cstdio>
#include<cstring>
const int p=1e9+7;
struct matrix
{
    long long a[111][111];
    int x,y;
    matrix(){memset(a,0,sizeof(a));}
    matrix cross(matrix a,matrix b)//乘
    {
        matrix m;
        m.x=a.x;
        m.y=b.y;
        for(int i=1;i<=a.x;i++)//a.y==b.x
            for(int j=1;j<=b.y;j++)
                for(int k=1;k<=a.y;k++)
                {
                    m.a[i][j]+=a.a[i][k]*b.a[k][j];
                    m.a[i][j]%=p;
                }
        return m;
    }
    void square()//平方
    {
        matrix m;
        m.x=x;
        m.y=y;
        for(int i=1;i<=x;i++)
            for(int j=1;j<=y;j++)
                for(int k=1;k<=x;k++)
                {
                    m.a[i][j]+=a[i][k]*a[k][j];
                    m.a[i][j]%=p;
                }
        *this=m;
    }
    matrix qpow(long long t)//快速幂
    {
        matrix m;
        m.x=x;
        m.y=y;
        for(int i=1;i<=x;i++)
            m.a[i][i]=1;
        matrix ans=*this;
        while(t)
        {
            if(t&1)
                m=cross(m,ans);
            ans.square();
            t>>=1;
        }
        return m;
    }
};
int main()
{
    int n;
    long long k;
    matrix a;
    scanf("%d%lld",&n,&k);
    a.x=n;
    a.y=n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%lld",&a.a[i][j]);
    a=a.qpow(k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            printf("%lld ",a.a[i][j]);
        printf("\n");
    }
    return 0;
}