常系数线性递推式的快速求单项值方法

前导知识

• 常系数线性递推式
  
  • 形如$f(n)=\sum_{i=1}^{k} a_if(n-i)$，其中$k$、$a_i$为常数的递推式，称为常系数线性递推式。
• Cayley-Hamilton定理
  
  • 对于矩阵$A$，$\det(\lambda E-A)$是一个$|A|$次多项式，称为A的特征多项式（characteristic polynomial），记为$g(\lambda)$。
  • 对于任意矩阵A，$g(A)=0$。
  • 证明参见任何一本高等代数教科书。
• 模多项式
  
  • 设$f$是n次多项式，$g$是m次多项式。
  • 存在多项式$k$、$l$，满足$kg+l=f$，且$l$的次数小于m。
  • 称$l$为$f$模$g$的余多项式。
  • 证明参见任何一本高等代数教科书。

正文

设有递推式$f(n)=\sum_{i=1}^{k} a_if(n-i)$，我们需要求$f(m)$。

通常而言，我们是构建一个k阶的矩阵$A$，称A为递推式的伴随矩阵（adjoint matrix）；构建一个向量$T$，其中$T_{1,i}=f(i)$，而$(TA^{m-k})_{1,1}$就是$f(m)$的值。构建$A$和$T$都是平凡的，这里不再赘述。

那么问题转化为求$(TA^p)_{1,1}$的值，而主要的瓶颈在于求$A^p$的值。

设$A^p=kg(A)+l$，其中$l$为$A^p$模$g(A)$的余多项式。容易发现$g(\lambda)=\lambda^{|A|}-\sum_{i=1}^{|A|} a_i \lambda^{|A|-i}$。由Cayley-Hamilton定理，$g(A)=0$，于是我们只需要关注$l$，也就是说我们只需要求出$A^p$模$g(A)$。这是简单的快速幂模多项式，使用FFT可以在$O(|A| \log |A| \log p)的时间内完成它$。

最终我们得到$A^p=\sum_{i=0}^{|A|-1} b_i A^i$。注意到我们现在仅关心$[T(\sum_{i=0}^{|A|-1} b_i A^i)]_{1,1}$，而对于$|A|-1 \ge i \ge 0$，$(TA^i)_{1,1}$都直接表示$f(i+1)$的值，这也就是递推的初值，于是答案就是$\sum_{i=0}^{|A|-1} b_if(i+1)$。

总时间复杂度为$O(k \log k \log m)$。