常系数齐次线性递推
给定递推式(f_n =a_1f_{n-1} + a_2 f_{n-2}...+a_k f_{n-k})。
给定(f_0,f_1...f_k)，求(f_n)。
先定义(f_n)的特征方程：(C(x) = x^{k} - a_1 x^{k-1} - a_2 x^{k-2}...-a_{k-1}x - a_k)。
求齐次线性递推通项式
由基本代数定理，(C(x) = 0) 的解(称为特征根)有(K)个，设为(alpha_1)、(alpha_2...alpha_K)。
有(f_n)的母函数(G(x) = frac{P(x)}{(1-alpha_1 x)(1-alpha_2 x)...(1-alpha_K x)})。
对于非重根(alpha)，它在通项公式(T_n)中的贡献形如(A alpha^n)，其中(A)为待定系数。
对于重根(eta)，设其为(r)重根，它在通项公式中的贡献形如((sum_{i=1}^r h_i n^{r-i} )eta^n)。
根据上述把通项式(T_n)列出来，利用前(K)项待定系数即可得到通项公式。
求齐次线性递推式
定义向量(A_i = (f_i,f_{i+1},f_{i+2}...f_{i+k-1}))，定义转移矩阵(M)。
初始我们知道(A_0 = (f_0,f_1,f_2...f_{k-1}))，现在要求(f_n)，即求(A_n = (f_n,f_{n+1}...f_{n+k-1}))。
可以矩阵快速幂(A_0*M^{n})，复杂度(O(k^3logn))。
将转移矩阵(M)带入特征多项式有：(F(M) = M^k - sum_{i=1}^k a_i M^{k-i})。
根据某定理，我们有(F(M) = 0)，所以我们可以对(M^n)化简，即(M^n equiv G(M) (mod F(M)))。
即我们求出(G(M))，那么(A_0G(M))与(A_0M^n)等价。
(A_n = A_0G(M) = A_0sum_{i=0}^{k-1} g_i M^i)，其中(g_i)即我们多项式取模后第(i)项的系数。
然后(A_n = sum_{i=0}^{k-1} g_i A_0M^i)。我们只需要求(f_n)，即只需要知道向量(A)的第一项。
所以(A = A_0M^i)的第一项是什么？不就是(f_i)吗！而(f_i,iin [0,k-1])我们事先知道。
所以(f_n = sum_{i=0}^{k-1} g_i f_i)。
实现上，关键在于求(G(x))，显然(M^n)我们不能一开始就把它存成一个多项式，所以需要倍增。
倍增的同时需要多项式乘法与多项式取模，
暴力做的话总复杂度为(O(k^2logn))，使用多项式运算复杂度为(O(klogklogn))。