※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: https://leetcode.com/problems/n-th-tribonacci-number/description
: 1137. N-th Tribonacci Number
: 給你一個數字n，求出第 n 個 Tribonacci 數列是多少。
沒寫過快速冪版本 精華區 z-14-2-3-7-4-2 有解釋
總之就是用轉移矩陣的快速冪把複雜度壓成log(n)
Python code:
class Solution:
def tribonacci(self, n: int) -> int:
trans = [[0,1,0],[0,0,1],[1,1,1]]
res = [[0],[1],[1]]
if n < 3:
return res[n][0]
def matmul(a, b, col):
res = [[0]*col for _ in range(3)]
for i in range(3):
for j in range(col):
for k in range(3):
res[i][j] += a[i][k]*b[k][j]
return res
n -= 2
while n:
if n%2:
res = matmul(trans, res, 1)
n //= 2
trans = matmul(trans, trans, 3)
return res[2][0]