常系数线性递推

如果一个递推关系中的所有系数均是常数，那么称之为常系数线性递推。
比如 $f_i = f_{i - 1} + f_{i - 2}$

如果 $i$ 出现在了系数的位置上，比如 $f_i = (i - 1)(f_{i - 1} + f_{i - 2})$ 就不是常系数递归。

值得注意的是类似 $f_i = f_{i - 1} + f_{i - 2} + i$ 的递推，虽然和普通的递归不太一样，但也可以用矩阵乘法来计算。

必须是常系数线性递推才可以矩阵乘法优化
如果系数中出现了 i 之类的，就不能矩阵乘法优化
f[i] = i * f[i-1]
阶乘是不能优化的

常系数线性递推的例子
f[i] = f[i-1] + f[i-2]
f[i] = f[i-1] + f[i-2] + 1
f[i] = f[i-1] + f[i-2] + 1 + i + i * i

f[i] = a * f[i-1] + b * g[i-1]
g[i] = c * f[i-1] + d * g[i-1]

不是常系数线性递推的例子
f[i] = i * f[i-1]
f[i] = (i-1) * (f[i-1] + f[i-2])
f[i] = f[i-1] + sqrt(i)

矩阵乘法

简单的例子
Fibonacci数

f[i] = f[i-1] + f[i-2]
x^i = x^(i-1) + x^(i-2)
x^2 = x + 1
解得 x1 x2
f[n] = x1^n 是合法的解
f[n] = x2^n 是合法的解

f[n] = c1 x1^n + c2 x2^n 也是合法的解
c1 x1^n + c2 x2^n = (c1 x1^(n-1) + c2 x2^(n-1)) + (c1 x1^(n-2) + c2 x2^(n-2))

x^2 - x - 1

f[8] = r[1] f[1] + r[0] f[0] 求 r[1] 和 r[0]
x^8 % (x^2 - x - 1) = r[1] x + r[0]

了解行列式的概念

了解特征多项式的概念

把转移矩阵M 带入特征多项式结果是 0 矩阵

M^n = q(M) (M^2 - M - I) + r(M)
q(M) 和 r(M) 都是关于M的多项式，其中r(M)的次数小于特征多项式的次数
注意到 (M^2 - M - I) 是 0 矩阵

M^n = r(M)
关键在于求出多项式r
x^n % (x^2 - x - 1)
直接进行多项式取模
n那么大，怎么取模？
倍增 / 快速幂

x^n % (x^2000 - x - 1)
计算这个的结果
n = 10 ** 18
所有运算都在mod 20092010

x^1 % (x^2000 - x - 1)
x^2 % (x^2000 - x - 1)
...
x^(2**60) % (x^2000 - x - 1)
每一个的结果都是一个 2000 项目