线性递推

问题描述

数列{a[n]}满足递推关系：a[n] = c[k]*a[n-1] + c[k-1]*a[n-2] + … + c[1]*a[n-k] + c[0]，给定初始项，求a[n]。

求解方法

将推递式写成矩阵形式：

| a[n]    |   | c[k] c[k-1] c[k-2] ... c[1] c[0] |   | a[n-1]   |
| a[n-1]  |   | 1    0      0      ... 0    0    |   | a[n-2]   |
| a[n-2]  | = | 0    1      0      ... 0    0    | * | a[n-3]   |
| ...     |   | ...  ...    ...    ...      ...  |   | ...      |
| a[n-k+1]|   | 0    0      0      ... 0    0    |   | a[n-k]   |
| 1       |   | 0    0      0      ... 0    1    |   | 1        |

由于矩阵乘法满足结合律，可先将矩阵相乘，这步可用快速幂进行优化，将计算次数从O(n)降到O(logn)。

除了求通项公式a[n]外，前n项和s[n]也可通过矩阵快速幂来求。以fib数列为例：

a[n]   = a[n]
a[n+1] = a[n] + a[n-1]
s[n+1] = s[n] + a[n+1] = s[n] + a[n] + a[n-1]

由此可构造递推矩阵：

| s[n+1] |   | 1  1  1 |   | s[n]   |
| a[n+1] | = | 0  1  1 | * | a[n]   |
| a[n]   |   | 0  1  0 |   | a[n-1] |