考虑这样一个问题

给定$n$阶矩阵$\textbf{A}(n \le 50)$，求$\textbf{S} = \sum_{k=0}^{m} {\textbf{A} ^ k},(0 \le m \le 10 ^ 9)$。

矩阵幂求和？我会二分！其实二分也是也是一种不错的方法，不过还有一种方法。我们来分析一下。

二分法

对次数进行二分，递归求出$m/2$次的答案，利用前$m/2$次答案求出后$m/2$次的答案，$m=$奇数时需要一些处理。

时间复杂度$O(n ^ 3 \log m)$。

构造矩阵法

矩阵的幂求和还能构造矩阵吗？先来看一个简化版的问题：

等比数列$f(0) = 1,f(n)=a f(n-1)$，求下述数列的第$n$项，将答案$\mod 10 ^ 9 + 7$输出

$$S(n) = \sum_{i=0}^{n} {f(n)}$$

对于这个问题，我们构造矩阵

$$\begin{bmatrix} f(n) \\ S(n) \end{bmatrix} = \begin{bmatrix} a & 0 \\ a & 1 \end{bmatrix} \begin{bmatrix} f(n-1) \\ S(n-1) \end{bmatrix}$$

将矩阵展开，有

$$\begin{bmatrix} f(n) \\ S(n) \end{bmatrix} = \begin{bmatrix} a & 0 \\ a & 1 \end{bmatrix} ^ n \begin{bmatrix} 1 \\ 1 \end{bmatrix}$$

现在我们可以解决矩阵版的问题了。矩阵的运算和整数的运算在许多方面是相像的，类似地，我们定义$k$阶单位阵为$\textbf{1}_k$，$k$阶零矩阵为$\textbf{0}_k$，设$f(m) = \textbf{A} ^ m,S(m) = \sum_{i=0}^{m} {f(i)}$，则我们可以构造出$2n$阶转移矩阵

$$\begin{bmatrix} f(m) \\ S(m) \end{bmatrix} = \begin{bmatrix} \textbf{A} & \textbf{0}_n \\ \textbf{A} & \textbf{1}_n \end{bmatrix} \begin{bmatrix} f(m-1) \\ S(m-1) \end{bmatrix} = \begin{bmatrix} \textbf{A} & \textbf{0}_n \\ \textbf{A} & \textbf{1}_n \end{bmatrix} ^ m \begin{bmatrix} \textbf{1}_n \\ \textbf{1}_n \end{bmatrix}$$

在这样的转移中，$f(m) = \textbf{A} f(m-1),S(m) = S(m-1) + f(m)$，满足题意。

时间复杂度$O(n ^ 3 \log m)$，常数略大，但较易理解。