N-th Tribonacci Number

easy ~15 min

The Tribonacci sequence starts T0 = 0, T1 = 1, T2 = 1, and each later term is the sum of the three before it: T(n) = T(n-1) + T(n-2) + T(n-3). So it goes 0, 1, 1, 2, 4, 7, 13, 24, 44, ...

Write two functions:

tribonacci(n: int) -> int: the exact value of T(n) for 0 ≤ n ≤ 37. A loop that keeps just the last three values is all you need.
tribonacci_mod(n: int) -> int: T(n) mod 1_000_000_007 for 0 ≤ n ≤ 10^18. A loop can't reach n = 10^18; aim for O(log n) arithmetic operations.

tribonacci(4)          # 4
tribonacci(25)         # 1389537
tribonacci_mod(4)      # 4
tribonacci_mod(100)    # 92295268
tribonacci_mod(10**18) # 926781415

Show hint

One step of the recurrence is a linear map on the vector (T(k+2), T(k+1), T(k)), so it can be written as a fixed 3×3 matrix. Jumping n steps means raising that matrix to the n-th power, which repeated squaring does in O(log n) multiplications (reduce mod p each time).

Topic: Matrix exponentiation. Linear recurrences in O(k^3 log n).