PART1 矩阵乘法

矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数（column）和第二个矩阵的行数（row）相同时才有意义 。一般单指矩阵乘积时，指的便是一般矩阵乘积。一个m×n的矩阵就是m×n个数排成m行n列的一个数阵。由于它把许多数据紧凑的集中到了一起，所以有时候可以简便地表示一些复杂的模型。

e.g.

PART 2 快速幂

快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。

PART3 矩阵快速幂

顾名思义，矩阵快速幂就是以快速幂的思想进行矩阵乘法（），代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

struct node{

      long long g[1001][1001];

}res;

int n;

node operator * (node a,node b){

      node c;

      long long x;

      for(int i=1;i<=n;i++)

         for(int j=1;j<=n;j++){

             x=0;

             for(int k=1;k<=n;k++)

                x+=(a.g[i][k]*b.g[k][j])%1000000007;

             c.g[i][j]=(x)%1000000007;

         }

      return c;

}

void go(node a,long long k){

      res=a;

      while(k){

          if(k&1){

              res=res*a;

          }

          a=a*a;

          k>>=1;

      }

}

int main()

{     int m,i,j;

      long long k;

      node a;

      cin>>n>>k;

      for(i=1;i<=n;i++)

         for(j=1;j<=n;j++){

             scanf("%lld",&a.g[i][j]);

         }

      go(a,k-1);

      for(i=1;i<=n;i++){

         for(j=1;j<=n;j++){

             printf("%lld ",res.g[i][j]);

         }

         puts("");

      }

      return 0;

}