楼主:
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时，其中一个想法就是这个