01
矩阵相乘需要前面矩阵的行数与后面矩阵的列数相同方可相乘。第一步，先将前面矩阵的每一行分别与后面矩阵的列相乘，作为结果矩阵的行列；第二步算出结果即可。
矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数(column)和第二个矩阵的行数(row)相同时才有意义 。一般单指矩阵乘积时，指的便是一般矩阵乘积。一个m×n的矩阵就是m×n个数排成m行n列的一个数阵。由于它把许多数据紧凑的集中到了一起，所以有时候可以简便地表示一些复杂的模型。矩阵相乘需要前面矩阵的行数与后面矩阵的列数相同方可相乘。第一步，先将前面矩阵的每一行分别与后面矩阵的列相乘，作为结果矩阵的行列；第二步算出结果即可。
注意事项：
1、当矩阵A的列数等于矩阵B的行数时，A与B可以相乘。
2、矩阵C的行数等于矩阵A的行数，C的列数等于B的列数。
3、乘积C的第m行第n列的元素等于矩阵A的第m行的元素与矩阵B的第n列对应元素乘积之和。
乘法结合律： (AB)C=A(BC)
乘法左分配律：(A+B)C=AC+BC
乘法右分配律：C(A+B)=CA+CB
对数乘的结合性k(AB)=(kA)B=A(kB)
矩阵乘法在以下两种情况下满足交换律。
AA*=A*A，A和伴随矩阵相乘满足交换律。
AE=EA，A和单位矩阵或数量矩阵满足交换律。
还有其他一些特殊的“乘积”形式被定义在矩阵上，值得注意的是，当提及“矩阵相乘”或者“矩阵乘法”的时候，并不是指代这些特殊的乘积形式，而是定义中所描述的矩阵乘法。在描述这些特殊乘积时，使用这些运算的专用名称和符号来避免表述歧义。

理解矩阵乘法
考研需要考一门课《线性代数》，这门课其实是教矩阵。
刚学的时候，还蛮简单的，矩阵加法就是相同位置的数字加一下。
矩阵乘法也类似，矩阵乘以一个常数，就是所有位置都乘以这个数。
但是，等到矩阵乘以矩阵的时候，一切就不一样了。
这个结果是怎么算出来的？
教科书告诉你，计算规则是，第一个矩阵第一行的每个数字（2 和 1），各自乘以第二个矩阵第一列对应位置的数字（1 和 1），然后将乘积相加（ 2 x 1 + 1 x 1），得到结果矩阵左上角的那个值 3。
也就是说，结果矩阵第 
 行与第 
 列交叉位置的那个值，等于第一个矩阵第 
 行与第二个矩阵第 
 列，对应位置的每个值的乘积之和。
怎么会有这么奇怪的规则？
我一直没理解这个规则的含义，导致《线性代数》这门课就没学懂。研究生时发现，线性代数是向量计算的基础，很多重要的数学模型都要用到向量计算，所以我做不了复杂模型。这一直让我有点伤心。
前些日子，受到一篇文章的启发，我终于想通了，矩阵乘法到底是什么东西。关键就是一句话，矩阵的本质就是线性方程式，两者是一一对应关系。如果从线性方程式的角度，理解矩阵乘法就毫无难度。
下面是一组线性方程式：
矩阵的最初目的，只是为线性方程组提供一个简写形式。
老实说，从上面这种写法，已经能看出矩阵乘法的规则了：系数矩阵第一行的 2 和 1，各自与 
 和 
 的乘积之和，等于 3。不过，这不算严格的证明，只是线性方程式转为矩阵的书写规则。
下面才是严格的证明：有三组未知数 
、
 和 
，其中 
 和 
 的关系如下：
 和 
 的关系如下：
有了这两组方程式，就可以求 
 和 
 的关系。从矩阵来看，很显然，只要把第二个矩阵代入第一个矩阵即可。
从方程式来看，也可以把第二个方程组代入第一个方程组：
上面的方程组可以整理成下面的形式:
最后那个矩阵等式，与前面的矩阵等式一一对照，就会得到下面的关系。
矩阵乘法的计算规则，从而得到证明。

理解矩阵乘法
作者：「小海考研人」
考研需要考一门课《线性代数》，这门课其实是教矩阵。
刚学的时候，还蛮简单的，矩阵加法就是相同位置的数字加一下。
矩阵乘法也类似，矩阵乘以一个常数，就是所有位置都乘以这个数。
但是，等到矩阵乘以矩阵的时候，一切就不一样了。
这个结果是怎么算出来的？
教科书告诉你，计算规则是，第一个矩阵第一行的每个数字（2 和 1），各自乘以第二个矩阵第一列对应位置的数字（1 和 1），然后将乘积相加（ 2 x 1 + 1 x 1），得到结果矩阵左上角的那个值 3。
也就是说，结果矩阵第 
 行与第 
 列交叉位置的那个值，等于第一个矩阵第 
 行与第二个矩阵第 
 列，对应位置的每个值的乘积之和。
怎么会有这么奇怪的规则？
我一直没理解这个规则的含义，导致《线性代数》这门课就没学懂。研究生时发现，线性代数是向量计算的基础，很多重要的数学模型都要用到向量计算，所以我做不了复杂模型。这一直让我有点伤心。
前些日子，受到一篇文章的启发，我终于想通了，矩阵乘法到底是什么东西。关键就是一句话，矩阵的本质就是线性方程式，两者是一一对应关系。如果从线性方程式的角度，理解矩阵乘法就毫无难度。
下面是一组线性方程式：
矩阵的最初目的，只是为线性方程组提供一个简写形式。
老实说，从上面这种写法，已经能看出矩阵乘法的规则了：系数矩阵第一行的 2 和 1，各自与 
 和 
 的乘积之和，等于 3。不过，这不算严格的证明，只是线性方程式转为矩阵的书写规则。
下面才是严格的证明：有三组未知数 
、
 和 
，其中 
 和 
 的关系如下：
 和 
 的关系如下：
有了这两组方程式，就可以求 
 和 
 的关系。从矩阵来看，很显然，只要把第二个矩阵代入第一个矩阵即可。
从方程式来看，也可以把第二个方程组代入第一个方程组：
上面的方程组可以整理成下面的形式:
最后那个矩阵等式，与前面的矩阵等式一一对照，就会得到下面的关系。
矩阵乘法的计算规则，从而得到证明。

矩阵并不是一个数而是可以表示一个比较复杂的模型（集合），而集合里封装着任意类型的值，而矩阵乘法则是一个比较重要的一个运算方式。
先说一下矩阵乘法的定义：
矩阵乘以矩阵的时候。

这个结果是怎么算出来的？
 
也就是说，结果矩阵第m行与第n列交叉位置的那个值，等于第一个矩阵第m行与第二个矩阵第n列，对应位置的每个值的乘积之和。
公式则是：其中cij为A的第i行与B的第j列对应乘积的和，即:
Cij =Σaik*bkj(1<=i<=n,1<=j<=n,1<=k<=n)。
Example(线性方程式)

矩阵的最初目的，只是为线性方程组提供一个简写形式。

附矩阵乘法的代码

const int N=100;  
int c[N][N];  //c是最终的矩阵
void multi(int a[][N],int b[][N],int n)  
{  
    memset(c,0,sizeof c);  
    for(int i=1;i<=n;i++)  
        for(int j=1;j<=n;j++)  
        　　for(int k=1;k<=n;k++)  
        　　　　c[i][j]+=a[i][k]*b[k][j];  
} 

快速幂
求幂时我们常常会因结果太大而导致速度很慢，这时候我们就需要运用倍增的思想特殊的乘法应运而生————快速幂。
举个例子，如果求a10，我们需要求十次，而如果我们用了快速幂就可以把a10转变为二进制的形式从而加快运算速度。
而我们又知道ai=(ai/2)2

因此就有如下代码
总的来说就是把指数变小，底数变大，让运算次数变小的过程。（感觉我就这句话写的有用

int fastpow(int a,int i)
{
    int ans=1;//ans是最后的结果
    int res=a;//res就相当于上文中的a的i-1次方。
    while (i>0)
    {
        if (i%2==1)//因为当I是奇数的时候你就不能再把它分成2进制啦
            ans=ans*res;//这时候就将res乘上去
        res=res*res;//底数不停变大
        i=i/2;指数缩小
    }
    return ans;
}

接下来就是矩阵快速幂了。
根据以上赘述，如果一个数能快速幂。那么一个矩阵也能快速幂。
原因：只要满足结合律的数学运算就都可以使用快速幂
把快速幂与矩阵乘法相结合就是矩阵快速幂，其中快速幂的过程并不需要修改，只要定义一个关于矩阵的结构体并重载一下乘法运算符就可以了,为了方便运算，同时尽量满足矩阵乘法的性质，下面的矩阵都是n*n的。
 这就是矩阵乘法代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,k;
const long long MOD=1000000007;
struct Matrix
{
  long long m[100][100];
};
Matrix A,E,ANS;
Matrix cheng(Matrix X,Matrix Y)
{
  Matrix C;
  for(long long i=1; i<=n; i++)
    for(long long j=1; j<=n; j++)
      {
        C.m[i][j]=0;
        for(long long l=1; l<=n; l++)
          C.m[i][j]=(C.m[i][j]+(X.m[i][l]*Y.m[l][j]))%MOD;
      }
  return C;
}
Matrix qsort(Matrix X,long long p)
{
  Matrix S=E;
  while(p)
    {
      if(p&1) S=cheng(S,X);
      X=cheng(X,X);
      p>>=1;
    }
  return S;
}
int main()
{
  scanf("%lld%lld",&n,&k);
  for(long long i=1; i<=n; i++)
    E.m[i][i]=1;
  for(long long i=1; i<=n; i++)
    for(long long j=1; j<=n; j++)
      scanf("%lld",&A.m[i][j]);
  ANS=qsort(A,k);
  for(long long i=1; i<=n; i++)
    {
      for(long long j=1; j<=n; j++)
        printf("%lld ",ANS.m[i][j]);
      puts("");
    }
  return 0;
}

 
这个有什么用呢，我们下面再说。
矩阵优化
利用矩阵，我们可以优化许多有关于递推和动态规划的问题。 我们先看一个简单的例子：斐波那契数列 我们知道斐波那契数列的递推式是
F[i]=F[i−1]+F[i−2]。
但是这样递推在i很大的时候效率不高，并且若不用滚动操作，空间消耗也很大。
所以我们可以转变为：

求F(n)等于求二阶矩阵的n - 1次方，结果取矩阵第一行第一列的元素。（因为要取矩阵的第一行才是Fn）。
问题转换为二阶矩阵的n次幂。
而计算二阶矩阵的N次幂运算，由于矩阵乘法满足结合律，这样，可以快速计算二阶矩阵的n次幂运算。
 
转载于:https://www.cnblogs.com/liuwenyao/p/8514920.html