AC. 梦想

frank_c1

矩阵幂求和

发布于2016年03月16日 | 暂无评论 | 741阅读 | 线性代数

考虑这样一个问题

给定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}_kk阶零矩阵为\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),常数略大,但较易理解。