最近写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 需要引入矩阵快速幂算法.