【概述】

線性遞推關系是組合計數中一種常見的遞推關系，關系式為：

最著名的線性遞推關系就是 Fibonacci 數列，有：f(1)=f(2)=1,f(n)=f(n-1)+f(n-2)

對于線性遞推關系，直接利用遞推式，需要在 O(nd) 的時間內才能求出 F(n)，時間無法承受，可以考慮借助矩陣來進行優化。

現在已經有了：，那么再加上??這種顯然成立的式子，于是有：

根據矩陣乘法的定義，即有：，于是可以利用矩陣快速冪來解決，時間復雜度僅為

例如，對于遞推公式：

可以構造矩陣：

化簡后：

由于 f(0)=0，f(1)=1，那么有：

故答案為：

因此矩陣快速冪求出 A 后即得答案

關于矩陣快速冪：點擊這里

【例題】

Reading comprehension（HDU-4990）：點擊這里

233 Matrix（HDU-5051）：點擊這里

Jzzhu and Sequences（CF-450B）：點擊這里

Bear in the Field（CF-385E）：點擊這里

M斐波那契數列（HDU-4549）(斐波那契矩陣構造+費馬小定理)：點擊這里

總結

以上是生活随笔為你收集整理的线性代数 —— 线性递推关系的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。