1class Solution {
2    // Calculates the n-th Tribonacci number
3    public int tribonacci(int n) {
4        // Base cases for n = 0, 1, 2
5        if (n == 0) {
6            return 0;
7        }
8        if (n < 3) {
9            return 1;
10        }
11        // Transformation matrix for Tribonacci sequence
12        int[][] transformationMatrix = {{1, 1, 0}, {1, 0, 1}, {1, 0, 0}};
13        // Calculate the power of the matrix to (n-3), since we know the first three values
14        int[][] resultingMatrix = matrixPower(transformationMatrix, n - 3);
15        // Initialize answer
16        int answer = 0;
17        // Add the top row of the matrix to get the answer
18        for (int element : resultingMatrix[0]) {
19            answer += element;
20        }
21        return answer;
22    }
23
24    // Multiplies two matrices and returns the result
25    private int[][] matrixMultiply(int[][] a, int[][] b) {
26        int rows = a.length, cols = b[0].length;
27        int[][] resultMatrix = new int[rows][cols];
28        // Perform matrix multiplication
29        for (int i = 0; i < rows; ++i) {
30            for (int j = 0; j < cols; ++j) {
31                for (int k = 0; k < b.length; ++k) {
32                    resultMatrix[i][j] += a[i][k] * b[k][j];
33                }
34            }
35        }
36        return resultMatrix;
37    }
38
39    // Calculates the matrix exponentiation of matrix 'a' raised to the power of 'n'
40    private int[][] matrixPower(int[][] a, int n) {
41        // Create an identity matrix for initial result
42        int[][] result = {{1, 1, 0}};
43        // Loop to do binary exponentiation
44        while (n > 0) {
45            // Multiply with 'a' when the least significant bit is 1
46            if ((n & 1) == 1) {
47                result = matrixMultiply(result, a);
48            }
49            // Square the matrix 'a'
50            a = matrixMultiply(a, a);
51            // Right shift 'n' to process the next bit
52            n >>= 1;
53        }
54        return result;
55    }
56}
57

1#include <vector>
2#include <numeric>
3
4class Solution {
5public:
6    // Computes the n-th Tribonacci number using matrix exponentiation
7    int tribonacci(int n) {
8        // Base case when n is 0
9        if (n == 0) {
10            return 0;
11        }
12        // Base cases for n being 1 or 2
13        if (n < 3) {
14            return 1;
15        }
16        // Initial transformation matrix
17        std::vector<std::vector<long long>> transformationMatrix = {
18            {1, 1, 0}, 
19            {1, 0, 1}, 
20            {1, 0, 0}
21        };
22        // Raise the transformation matrix to the power (n - 3)
23        std::vector<std::vector<long long>> resultMatrix = matrixPower(transformationMatrix, n - 3);
24        // The sum of the first row of the result matrix gives us the nth Tribonacci number
25        return std::accumulate(resultMatrix[0].begin(), resultMatrix[0].end(), 0);
26    }
27
28private:
29    using ll = long long; // Alias for long long type for easier reading
30
31    // Multiplies two matrices and returns the result
32    std::vector<std::vector<ll>> matrixMultiply(std::vector<std::vector<ll>>& a, std::vector<std::vector<ll>>& b) {
33        int rows = a.size(), columns = b[0].size();
34        std::vector<std::vector<ll>> product(rows, std::vector<ll>(columns));
35      
36        for (int i = 0; i < rows; ++i) {
37            for (int j = 0; j < columns; ++j) {
38                for (int k = 0; k < b.size(); ++k) {
39                    product[i][j] += a[i][k] * b[k][j];
40                }
41            }
42        }
43        return product;
44    }
45
46    // Calculates the power of a matrix to the given exponent n
47    std::vector<std::vector<ll>> matrixPower(std::vector<std::vector<ll>>& a, int n) {
48        // Starting with the identity matrix of size 3x3
49        std::vector<std::vector<ll>> result = {
50            {1, 0, 0}, 
51            {0, 1, 0}, 
52            {0, 0, 1}
53        };
54      
55        while (n) {
56            if (n & 1) { // If n is odd, multiply the result by the current matrix a
57                result = matrixMultiply(result, a);
58            }
59            a = matrixMultiply(a, a); // Square the matrix a
60            n >>= 1; // Divide n by 2
61        }
62        return result;
63    }
64};
65

1// Calculates the n-th Tribonacci number using matrix exponentiation.
2function tribonacci(n: number): number {
3    // Base cases for n = 0, 1, and 2.
4    if (n === 0) {
5        return 0;
6    }
7    if (n < 3) {
8        return 1;
9    }
10  
11    // Matrix representation of the Tribonacci relation.
12    const tribonacciMatrix = [
13        [1, 1, 0],
14        [1, 0, 1],
15        [1, 0, 0],
16    ];
17  
18    // Raise the matrix to the (n-3)-th power and sum the top row for the result.
19    return matrixPower(tribonacciMatrix, n - 3)[0].reduce((sum, element) => sum + element);
20}
21
22// Multiplies two matrices and returns the result.
23function multiplyMatrices(matrix1: number[][], matrix2: number[][]): number[][] {
24    const rows = matrix1.length;
25    const cols = matrix2[0].length;
26    // Create an empty matrix for the result.
27    const result = Array.from({ length: rows }, () => Array.from({ length: cols }, () => 0));
28  
29    // Calculate the product of the two matrices.
30    for (let i = 0; i < rows; ++i) {
31        for (let j = 0; j < cols; ++j) {
32            for (let k = 0; k < matrix2.length; ++k) {
33                result[i][j] += matrix1[i][k] * matrix2[k][j];
34            }
35        }
36    }
37  
38    return result;
39}
40
41// Raises a matrix to the power of n and returns the result.
42function matrixPower(matrix: number[][], n: number): number[][] {
43    // Initialize the result as an identity matrix in the shape of a 1 x 3 matrix.
44    let result = [
45        [1, 1, 0],
46    ];
47  
48    while (n > 0) {
49        // If the exponent is odd, multiply the result by the matrix.
50        if (n & 1) {
51            result = multiplyMatrices(result, matrix);
52        }
53        // Square the matrix.
54        matrix = multiplyMatrices(matrix, matrix);
55        // Halve the exponent by right-shifting it.
56        n >>= 1;
57    }
58  
59    return result;
60}
61