最近寫Visa OA遇到的問題
問題:
假如有一個數字n, 你每次可以拿1個或3個請問有幾種不同組合?
範例1:
n = 7
所有的組合有9種, 回傳9:
[1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 3]
[1, 1, 1, 3, 1]
[1, 1, 3, 1, 1]
[1, 3, 1, 1, 1]
[3, 1, 1, 1, 1]
[1, 3, 3]
[3, 1, 3]
[3, 3, 1]
我用背包問題的解法, time complexity 是O(n), 可是會timeout, 因為 1 <= n <= 1e9,想請問一下有沒有log(N)的解法？
感謝大家

變形費氏數列 矩陣乘法求解3*3 矩陣 列出連續三項的公式，線性變換？的矩陣就會出來

本家費氏數列是取 1 或 2 個, 可以比較一下公式

取1，3，5公式就變成Fi=Fi-1+Fi-3+Fi-5

他的重點是有 10 億項，所以須要更快的方法

倒底是問幾種組合還是排列方式? 只要知道幾種還是要條列出來?要條列的話, n=1e9 會不會光印結果就超時了?

F(n) = F(n-1) + F(n-3),求 F(1,000,000,000)

抱歉, 請忽略我前面腦殘. 原PO 需要引入矩陣快速冪算法.