常係數齊次線性遞推

問題

給定一個線性遞推數列 \(\{f_i\}\) 的前 \(k\) 項 \(f_0\dots f_{k-1}\)，和其遞推式 \(f_n=\sum_{i=1}^k f_{n-i}a_i\) 的各項係數 \(a_i\)，求 \(f_n\)。

前置知識

做法

定義 \(F(\sum c_ix^i)=\sum c_if_i\)，那麼答案就是 \(F(x^n)\)。

由於 \(f_n=\sum_{i=1}^{k}f_{n-i}a_i\)，所以 \(F(x^n)=F(\sum_{i=1}^{k}a_ix^{n-i})\)，所以 \(F(x^n-\sum_{i=1}^k a_ix^{n-i})=F(x^{n-k}(x^k-\sum_{i=0}^{k-1}a_{k-i}x^i))=0\)。

設 \(G(x)=x^k-\sum_{i=0}^{k-1}a_{k-i}x^i\)。

那麼 \(F(A(x)+x^nG(x))=F(A(x))+F(x^nG(x))=F(A(x))\)。

那麼就可以通過多次對 \(A(x)\) 加上 \(x^nG(x)\) 的倍數來降低 \(A(x)\) 的次數。

也就是求 \(F(A(x)\bmod G(x))\)。\(A(x)\bmod G(x)\) 的次數不超過 \(k-1\)，而 \(f_{0..k-1}\) 已經給出了，就可以算了。

問題轉化成了快速地求 \(x^n\bmod G(x)\)，只要將普通快速冪中的乘法與取模換成多項式乘法與多項式取模就可以在 \(O(k\log k\log n)\) 的時間複雜度內解決這個問題了。

矩陣的解釋

該算法由 Fiduccia 在 1985 年提出，對於 \(t\geq 0\) 我們定義列向量 \(v_t\) 為

\[ v_t=\begin{bmatrix}f_t\\f_{t+1}\\\vdots\\f_{t+k-1}\end{bmatrix} \]

那麼不難發現

\[ \underbrace{\begin{bmatrix}f_{t+1}\\f_{t+2}\\\vdots\\f_{t+k}\end{bmatrix}}_{v_{t+1}}=\underbrace{\begin{bmatrix}&1&&\\&&\ddots&\\&&&1\\a_{k}&a_{k-1}&\cdots&a_{1}\end{bmatrix}}_M\times \underbrace{\begin{bmatrix}f_t\\f_{t+1}\\\vdots\\f_{t+k-1}\end{bmatrix}}_{v_t} \]

而因為 \(v_{t+k}\) 中每一行都滿足這個遞推關係，我們將 \(v_{t+k}\) 描述為一個線性組合如

\[ v_{t+k}=\sum_{i=1}^ka_{i}v_{t+k-i} \]

有

\[ M^kv_t=\sum_{i=1}^ka_{i}M^{k-i}v_{t} \]

發現若能將兩邊的 \(v_t\) 消去後得到多項式 \(\Gamma(x)=x^k-\sum_{i=1}^ka_ix^{k-i}\) 滿足 \(\Gamma(M)=O\) 其中 \(O\) 為一個 \(k\times k\) 的零矩陣。

假設我們要求 \(M^n\) 可以構造多項式 \(f(x)=x^n\) 那麼 \(f(M)=M^n\)，而現在我們可將 \(f(x)\) 寫成 \(f(x)=Q(x)\Gamma(x)+R(x)\) 而其中零矩陣是沒有貢獻的，那麼 \(f(M)=R(M)\)。

但是注意矩陣乘法不滿足消去律，此處我們定義矩陣 \(M\) 的特徵多項式為 \(\Gamma(x)=\det(xI-M)\)，其中 \(I\) 為一個 \(k\times k\) 的單位矩陣。Cayley–Hamilton 定理指出 \(\Gamma(M)=O\)，我們觀察 \(M\) 的形式較為特殊，為下 Hessenberg 矩陣，其特徵多項式比起一般矩陣更容易計算。

我們從右下角的 \(2\times 2\) 矩陣開始計算特徵多項式

\[ \Gamma_2(x)=\det\left(\begin{bmatrix}x&-1\\-a_2&x-a_1\end{bmatrix}\right)=x^2-a_1x-a_2 \]

右下角 \(3\times 3\) 矩陣按照第一行的餘子式展開有

\[ \begin{aligned} \Gamma_3(x)&=\det\left(\begin{bmatrix}x&-1&0\\0&x&-1\\-a_3&-a_2&x-a_1\end{bmatrix}\right)\\ &=x\cdot (-1)^{1+1}\cdot \Gamma_2(x)+(-1)\cdot (-1)^{1+2}\cdot \det\left(\begin{bmatrix}0&-1\\-a_3&x-a_1\end{bmatrix}\right)\\ &=x^3-a_1x^2-a_2x-a_3 \end{aligned} \]

觀察並歸納有

\[ \Gamma(x)=\Gamma_k(x)=x^k-\sum_{i=1}^ka_ix^{k-i} \]

至此我們可以使用上面的結論。令 \(g(x)=f(x)\bmod{\Gamma(x)}\) 有 \(g(M)=M^n\)。而 \(\deg(g(x))\lt k\) 顯然，令 \(g(x)=g_0+g_1x+\cdots +g_{k-1}x^{k-1}\) 那麼

\[ M^nv_0=\sum_{i=0}^{k-1}g_iM^iv_0 \]

即

\[ v_n=\sum_{i=0}^{k-1}g_iv_{i} \]

我們關注 \(v_0,v_1,\dots ,v_{k-1}\) 的第一行就是 \(f_0,f_1,\dots ,f_{k-1}\) 已知，那麼 \(f_n\) 可在 \(O(k)\) 時間簡單得到。求出 \(g(x)\) 則可用快速冪和多項式取模與上述解釋是一樣的。該算法常數較大，使用生成函數可以得到一個常數更小的算法，見一種新的線性遞推計算方法。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用