矩阵运算法则

• 矩阵 A 的大小为 $n × m$， B 的大小为 $n × k$，设$C = A × B$
  则$C_{i,j}=\sum\limits^n_{k=1}A_{i,k}\times B_{k,j}$
  例如：
  $\begin{bmatrix}2 & 1\\4 & 3\end{bmatrix} \times \begin{bmatrix}1 & 2\\1 & 0\end{bmatrix} = \begin{bmatrix}2 \times 1 + 1 \times 1 & 2 \times 2 + 1 \times 0 \\4 \times 1 + 3 \times 1 & 4\times 2 + 3\times 0 \end{bmatrix} = \begin{bmatrix}3 & 4\\7 & 8\end{bmatrix}$

• 矩阵乘满足结合律：$(AB)C = A(BC)$

• 有一种特殊的矩阵：单位矩阵，它从左上角到右下角的对角线上的元素均为1，其他元素均为0。它在矩阵乘中相当于数乘中的1，即任何矩阵乘它都等于本身。
  例：
  $e = \begin{bmatrix}1 & 0\\0 & 1\end{bmatrix}$

以上这些就是学会矩阵快速幂前必备的基础知识。

代码实现

• 理解了矩阵乘法之后，我们可以用函数来模拟矩阵乘。

  Mat Mul(Mat x, Mat y) //矩阵乘
  {
      Mat c;
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++)
              c.m[i][j] = 0;
      for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++)
              for (int k = 1; k <= n; k++)
                  c.m[i][j] = (c.m[i][j] + x.m[i][k] * y.m[k][j] % mod) % mod;
      return c;
  }

• 因为矩阵乘满足结合律，所以快速幂完全适用于矩阵，矩阵快速幂和普通快速幂几乎一模一样，不同点在于乘号改成了 Mul 函数（不会普通快速幂的请前往P1226）

  Mat pow(Mat x, LL y) //矩阵快速幂
  {
      Mat ans = e;
      while (y)
      {
          if (y & 1)
              ans = Mul(ans, x);
          x = Mul(x, x);
          y >>= 1;
      }
      return ans;
  }

知道这些知识后，这道题基本就可以 AC 了。要注意开 long long，不然会爆零。

AC代码：

#include <iostream>
#include <cstring>
#define mod 1000000007
#define LL long long
using namespace std;
struct Mat
{
    LL m[101][101];
};        //结构体存矩阵
Mat a, e; //a是输入的矩阵，e是单位矩阵
LL n, p;
Mat Mul(Mat x, Mat y) //矩阵乘
{
    Mat c;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            c.m[i][j] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                c.m[i][j] = (c.m[i][j] + x.m[i][k] * y.m[k][j] % mod) % mod;
    return c;
}
Mat pow(Mat x, LL y) //矩阵快速幂
{
    Mat ans = e;
    while (y)
    {
        if (y & 1)
            ans = Mul(ans, x);
        x = Mul(x, x);
        y >>= 1;
    }
    return ans;
}
int main()
{
    //输入
    cin >> n >> p;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a.m[i][j];
    //算法核心
    for (int i = 1; i <= n; i++)
        e.m[i][i] = 1;
    Mat ans = pow(a, p);
    //输出
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << ans.m[i][j] % mod << " ";
        cout << endl;
    }
    return 0;
}

P.S. 关于用结构体的好处：向函数中传参和变量之间赋值比较方便。直接用二维数组当然也没什么问题