建议学习：> here <
一个线性变换会使一个向量在方向上发生偏移，但是如果能找到变换后方向不会发生偏移的向量，将其当作基向量，就可以快速计算递推式的任意项。
将这种基向量称作特征向量 $ \vec{v} $ ，每次变换后伸长或缩短的倍数称作特征值 $ \lambda $ ，转移矩阵为$ A $，其中 $ A $ 有 $ n $ 列（转移长度为 $ n $）。
于是：
$$
A \vec{v} = \lambda \vec{v}\\
(\lambda I - A) \vec{v} = 0
$$
其中 $ \vec{v} $ 取零向量是无意义的。
若要使 $ \vec{v} $ 为非零解，则 $ \det(\lambda I - A) = 0 $ ，即将空间降维。
其中 $ \det(\lambda I - A) = 0 $ 是次数为 $ A $ 的列数的特征多项式 $ f(\lambda) $ 。
根据Cayley-Hamilton定理， $ f(A) = 0 $ ，证明莫得感兴趣的话百度一下。
转移矩阵大概是长这样的：
$$
\begin{bmatrix}
a_1&a_2&a_3&\dots&a_{n-1}&a_n\\
1 &0 &0 &\dots&0&0 \\
0 &1 &0 &\dots&0&0 \\
\dots&\dots&\dots&\dots&\dots&\dots\\
0 &0 &0 &\dots&1&0
\end{bmatrix}
$$
特征多项式是长这样的：
$$
\det(\begin{bmatrix}
\lambda-a_1&-a_2&-a_3&\dots&-a_{n-1}&-a_n\\
-1 &\lambda &0 &\dots&0&0 \\
0 &-1 &\lambda &\dots&0&0 \\
\dots&\dots&\dots&\dots&\dots&\dots\\
0 &0 &0 &\dots&-1&\lambda
\end{bmatrix})
$$
这个东西的行列式可以手算（判断第一行选哪一个）：
$$
f(\lambda) = \lambda^n - \sum_{i = 1}^{n}a_i\lambda^{n-i}
$$
设初始项 $ H $，求第 $ m $ 项。
求 $ (A^{m} \times H)_0 $ 。
$$
\because f(A) = 0\\
\therefore A^m \bmod f(A) = A^m
$$
直接多项式快速幂 + 多项式取模计算出 $ A^m \bmod f(A) $ 。
设之后得到的多项式
$$
g(A) = \sum_{i = 0}^{n - 1} c_i A^i
$$
最后求
$$
\sum_{i = 0}^{n - 1} (c_{i} A^{i} H){0} = \sum{i = 0}^{n - 1} c_{i} h_{i}
$$
授之以渔不如授之以鱼
1 |
|