作者:
yueayase (scrya)
2023-02-26 01:30:54※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 1137. N-th Tribonacci Number
: 泰波拿契數被定義如下：
: F(0) = 0;
: F(1) = 1;
: F(2) = 1;
: F(n) = F(n-1) + F(n-2) + F(n-3);
: 給予一個n，求出他的泰波拿契數。
用DP complexity是O(n)，但這個可以做到complexity O(log n):
Idea: 把Recurrence轉成companion matrix和某個初始vector相乘:
寫成
F(n-2) = F(n-2)
F(n-1) = F(n-1)
F(n) = F(n-1)+F(n-2)+F(n-3)
令x(n) = [F(n-2)] [0 1 0]
[F(n-1)] , A = [0 0 1]
[F(n) ] [1 1 1]
=> x(n) = Ax(n-1) for n≧2
因為F(0) = 0, F(1) = 1, F(2) = 1
=> x(2) = [0]
[1]
[1]
2 3 n-2
=> x(n) = Ax(n-1) = A x(n-2)= A x(n-2) = ... = A x(2)
n-2
所以關鍵就是要如何快速算出A
而一個常見的做法就是快速乘法，pseudocode如下("/"是取商數，n為非負整數):
fastMultiply(A, n)
if(n == 0)
return I;
else if(n is even)
An = fastMultiply(A,n/2);
return An*An;
else
An = fastMultiply(A,n/2);
return An*An*A;
End
而C++實作如下:
https://leetcode.com/problems/n-th-tribonacci-number/submissions/904793003/
但因為測資的n最多只有37，所以看不出有明顯效果...
(也難怪... n太大就會overflow了... 若要處理這個，又要implement BigInteger class)
而如果不想用recursion實現快速矩陣乘法，可以用stack存n的binary representation
，最上層元素為最高位的bit:
stack<int> s;
while(n > 0){
s.push(n%2);
n /= 2;
}
vector<vector<int> > An = I;
while(!s.empty()){
if(s.top() == 1)
An = An*An*A;
else
An = An*An;
s.pop();
}
return An;
PS: 這個想法倒是ChatGPT在解Fibonacci number時，其中一個想法就是這個