※ 引述《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]