[問題] 面試再次遇到的問題

[phoenixrace (殘存亦陌路 兵敗如山倒)]

最近寫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)的解法？

感謝大家






--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.219.21.1
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1538349886.A.326.html
→ Morris1028: 變形費氏數列 矩陣乘法求解
我有想到這個, 可是要怎麽設定一開始的矩陣, 我就卡在這了, 一般的fib是2d matrix相乘, 可是這個我不知道從何下手
→ Morris1028: 3*3 矩陣 列出連續三項的公式，線性變換？的矩陣就會
→ Morris1028: 出來
再問個問題,為啥看得出來是Fib,是因為我們的取法只有1和3嗎？假如我們可以取1,3,5也可以用FIB計算嗎？
推 LPH66: 本家費氏數列是取 1 或 2 個, 可以比較一下公式
感謝 我再去研究看看
※ 編輯: phoenixrace (129.219.21.3), 10/01/2018 10:52:11
推 JameC: 取1，3，5公式就變成Fi=Fi-1+Fi-3+Fi-5
推 cutekid: 他的重點是有 10 億項，所以須要更快的方法
推 yvb: 倒底是問幾種組合還是排列方式? 只要知道幾種還是要條列出來?
→ yvb: 要條列的話, n=1e9 會不會光印結果就超時了?
推 cutekid: F(n) = F(n-1) + F(n-3),求 F(1,000,000,000)
推 yvb: 抱歉, 請忽略我前面腦殘. 原PO 需要引入矩陣快速冪算法.
已經知道怎麼解了, 感謝大家幫忙
※ 編輯: phoenixrace (24.251.165.125), 10/17/2018 03:41:26