特征多项式加速矩阵转移

· · 算法·理论

定义：

对于任意满足 f_i=A×f_{i-1}（其中 f_i 是长度为 k 的向量，A 是给定的 k×k 的转移矩阵）的递推形式，如果我们能快速求出 A 的特征多项式 \det (λI-A) 和 f_i 的前 k 项 f_0∼f_{k-1}，那么我们可以在 O(k \log k \log n) 时间复杂度内求出 f_n。1 维 k 阶常系数线性齐次递推和 k 维 1 阶常系数线性齐次递推通常都可以用该方法解决。

做法：

首先，我们需要写出对于相邻项之间的转移矩阵 A 满足 f_i=A×f_{i-1}，从而 f_n=A^n×f_0。定义 A 的特征多项式为一个关于 λ 的多项式 F(λ)=\det (λI-A)，我们采用手推矩阵的秩的方式求出 F(λ)，利用多项式取模，求出 R(x)=x^n \bmod F(x)（一般 n 很大，需要用快速幂来求，乘一次取一次模），于是我们有 f_n=\sum_{i=0}^{k-1}f_i×r_i，其中 r_i 是 R(x) 的 i 次项系数。我们还需要找到能够快速计算 f_{1∼k-1} 的方式，否则需要暴力递推。这样问题就得以解决了。

1 维 k 阶常系数线性齐次递推：

特别地，对于 1 维 k 阶递推式 f_i=p_0 f_{i-k}+p_1 f_{i-k+1}+⋯+p_{k-1} f_{i-1}，其特征多项式为 F(x)=-p_0-p_1 x-⋯-p_{k-1} x^{k-1}+x^k。

证明：

由 Hamilton-Cayley 定理可知，F(A) 一定为零矩阵，即 F(A)=0，又称 “矩阵的特征多项式是它的化零多项式”。我们设 R(x)=x^n \bmod F(x)，它也可以被写成 x^n=F(x)Q(x)+R(x) 的形式。代入 x=A，得 A^n=F(A)Q(A)+R(A)=R(A)。对于 A^n=R(A)，对其左右同时乘上 f_0，得 f_n=\sum_{i=0}^{k-1}f_i×r_i。于是我们只需要用多项式取模直接求出 R(x)，如做法中所述去实现就好了。

习题：

【模板】常系数齐次线性递推

P5915 冬至

EI 说还想让你优化一下这道题：ARC100F Colorful Sequences