\(n\le 10^9,m\le 10^4\)，需要求：

\[f_n = \sum_{k = 1}^m a_k*f_{n - k} \]

考虑用矩阵快速幂加速，设初始向量为 \(F_0 = [f_0, 0, 0,..., 0]\)，转移矩阵为 \(A\)，要求出 \({A^nF_0}_{(0)}\) 即第 \(0\) 项。

考虑若

\[A^n = \sum_{i = 0}^{m - 1} A^i*c_i \]

则

\({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\)。

考虑设：

\[P_A(\lambda) = |\lambda I - A| = \lambda^m - \sum_{i = 1}^m \lambda^{m - i} b_i \]

将 \(\lambda\) 变为 \(A\)，由 \(C-H\) 定理可得：

\[P_A(A) = 0 = A^m - \sum_{i = 1}^m A^{m - i} b_i \]

乘以 \(F_0\) 可得：

\[F_0A^m = \sum_{i = 1}^m F_{m - i} b_i \]

于是 \(b_m = 1, b_i = -a_{m - i}\)。

\[A^n = P_A(A)Q(A) + \sum_{i = 0}^{m - 1} c_i*A^i\\ x^n = \sum_{i = 0}^m c_i*x^i \bmod P_A(x)\]

于是通过多项式取模与快速幂就可以求出 \(c\)。