SAOKA

题解递推式转换矩阵方法总结

题解

/ 注册

递推式转换矩阵方法总结

1919 浏览 1 回复 2019-10-29

SAOKA

+关注

https://ac.nowcoder.com/acm/problem/14607

矩阵快速幂的使用，能够对于一个给定且不变的递推式，快速地得到我们要的第 $n$ 项，但是我们往往无法快速地推导出递推式，那么我们这里来总结一下。

步骤:

列出递推式中的元素
往前递推一项也列出对应元素
设基矩阵 $base$ 利用关系式以及矩阵乘法解出 $base$

举个栗子:

著名的斐波拉契数列:

$f[i] = f[i-1] + f[i-2]$

步骤一 :

我们可以发现，这是用 $f[i-1]$ 和 $f[i-2]$ 来求到 $f[i]$ ，那么矩阵中一定会包含至少两项与 $f$ 有关的变量，不妨设:

$\left[ \begin{matrix} f[i-1] & f[i-2]\\ \end{matrix} \right]$
$\times$
$base=$
$\left[ \begin{matrix} f[i] & f[i-1]\\ \end{matrix} \right]$

步骤二 : (解出 $base$ 矩阵)
由矩阵乘法的性质，我们可以反推得到 $base$ 矩阵的行列数应该是 $(2,2)$ ，不妨设:

$base= \left[ \begin{matrix} a & b\\ c & d\\ \end{matrix} \right]$

根据矩阵乘法:

$\begin{cases} f[i-1] \times a + f[i-2] \times b = f[i] \\ f[i-1] \times c + f[i-2] \times d = f[i-1] \\ \end{cases}$

最后可以解得:

$base= \left[ \begin{matrix} 1 & 1\\ 1 & 0\\ \end{matrix} \right]$

最后再利用矩阵快速幂就可以了！

对于本题:

递推式:

$a_n = 2a_{n-1} + n^2$

我们先不去想怎么处理这个 $n^2$ ，让我们先找出第 $n$ 项中应当包含的元素:

$a_n$ 、 $n^2$

以及前一项( $n-1$ 项)应当包含的元素:

$a_{n-1}$ 、 $(n-1)^2$

我们考虑如何从 $(n-1)^2$ 变换到 $n^2$ ，平方差可得:

$n^2=(n-1)^2+2n-1$

所以我们的递推式中必定会包含 $n^2$ 、 $n$ 、 $1$ 这三个元素(否则不能递推下去)

我们不妨设第 $n$ 项矩阵为:

$\left[ \begin{matrix} a_n & n^2 & n & 1 \\ \end{matrix} \right]$

第 $n-1$ 项矩阵为:

$\left[ \begin{matrix} a_{n-1} & {n-1}^2 & n-1 & 1 \\ \end{matrix} \right]$

设出并求出基矩阵 $base$ :

$base= \left[ \begin{matrix} 2 & 0 & 0 & 0\\ 1 & 1 & 0 & 0\\ 2 & 2 & 1 & 0\\ 1 & 1 & 1 & 1\\ \end{matrix} \right]$

接下来就可以用矩阵快速幂了！！(完结撒花)

举报

收藏

赞 6

评论加载中...