\(n\le 10^9,m\le 10^4\)，需要求：
考虑用矩阵快速幂加速，设初始向量为 \(F_0 = [f_0, 0, 0,..., 0]\)，转移矩阵为 \(A\)，要求出 \({A^nF_0}_{(0)}\) 即第 \(0\) 项。
考虑若
则
\({A^nF_0}_{(0)} = \sum_{i = 0}^{m - 1} c_i*({A^iF_0}_{(0)}) = \sum_{i = 0}^m c_i*f_i\)
然后就可以 \(O(m)\) 计算出 \(f_n\)。
考虑设：
将 \(\lambda\) 变为 \(A\)，由 \(C-H\) 定理可得：
乘以 \(F_0\) 可得：
于是 \(b_m = 1, b_i = -a_{m - i}\)。
于是通过多项式取模与快速幂就可以求出 \(c\)。
原文：https://www.cnblogs.com/iqx37f/p/14810597.html