The Tribonacci sequence Tn is defined as follows:
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
Given n, return the value of Tn.
Example 1:
Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4
Example 2:
Input: n = 25 Output: 1389537
Constraints:
0 <= n <= 37- The answer is guaranteed to fit within a 32-bit integer, ie.
answer <= 2^31 - 1.
class Solution:
def tribonacci(self, n: int) -> int:
a, b, c = 0, 1, 1
for _ in range(n):
a, b, c = b, c, a + b + c
return aclass Solution:
def tribonacci(self, n: int) -> int:
def mul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
m, n = len(a), len(b[0])
c = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
for k in range(len(a[0])):
c[i][j] = c[i][j] + a[i][k] * b[k][j]
return c
def pow(a: List[List[int]], n: int) -> List[List[int]]:
res = [[1, 1, 0]]
while n:
if n & 1:
res = mul(res, a)
n >>= 1
a = mul(a, a)
return res
if n == 0:
return 0
if n < 3:
return 1
a = [[1, 1, 0], [1, 0, 1], [1, 0, 0]]
return sum(pow(a, n - 3)[0])import numpy as np
class Solution:
def tribonacci(self, n: int) -> int:
if n == 0:
return 0
if n < 3:
return 1
factor = np.mat([(1, 1, 0), (1, 0, 1), (1, 0, 0)], np.dtype("O"))
res = np.mat([(1, 1, 0)], np.dtype("O"))
n -= 3
while n:
if n & 1:
res *= factor
factor *= factor
n >>= 1
return res.sum()class Solution {
public int tribonacci(int n) {
int a = 0, b = 1, c = 1;
while (n-- > 0) {
int d = a + b + c;
a = b;
b = c;
c = d;
}
return a;
}
}class Solution {
public int tribonacci(int n) {
if (n == 0) {
return 0;
}
if (n < 3) {
return 1;
}
int[][] a = {{1, 1, 0}, {1, 0, 1}, {1, 0, 0}};
int[][] res = pow(a, n - 3);
int ans = 0;
for (int x : res[0]) {
ans += x;
}
return ans;
}
private int[][] mul(int[][] a, int[][] b) {
int m = a.length, n = b[0].length;
int[][] c = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < b.length; ++k) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
return c;
}
private int[][] pow(int[][] a, int n) {
int[][] res = {{1, 1, 0}};
while (n > 0) {
if ((n & 1) == 1) {
res = mul(res, a);
}
a = mul(a, a);
n >>= 1;
}
return res;
}
}class Solution {
public:
int tribonacci(int n) {
long long a = 0, b = 1, c = 1;
while (n--) {
long long d = a + b + c;
a = b;
b = c;
c = d;
}
return (int) a;
}
};class Solution {
public:
int tribonacci(int n) {
if (n == 0) {
return 0;
}
if (n < 3) {
return 1;
}
vector<vector<ll>> a = {{1, 1, 0}, {1, 0, 1}, {1, 0, 0}};
vector<vector<ll>> res = pow(a, n - 3);
return accumulate(res[0].begin(), res[0].end(), 0);
}
private:
using ll = long long;
vector<vector<ll>> mul(vector<vector<ll>>& a, vector<vector<ll>>& b) {
int m = a.size(), n = b[0].size();
vector<vector<ll>> c(m, vector<ll>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < b.size(); ++k) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
return c;
}
vector<vector<ll>> pow(vector<vector<ll>>& a, int n) {
vector<vector<ll>> res = {{1, 1, 0}};
while (n) {
if (n & 1) {
res = mul(res, a);
}
a = mul(a, a);
n >>= 1;
}
return res;
}
};func tribonacci(n int) int {
a, b, c := 0, 1, 1
for i := 0; i < n; i++ {
a, b, c = b, c, a+b+c
}
return a
}func tribonacci(n int) (ans int) {
if n == 0 {
return 0
}
if n < 3 {
return 1
}
a := [][]int{{1, 1, 0}, {1, 0, 1}, {1, 0, 0}}
res := pow(a, n-3)
for _, x := range res[0] {
ans += x
}
return
}
func mul(a, b [][]int) [][]int {
m, n := len(a), len(b[0])
c := make([][]int, m)
for i := range c {
c[i] = make([]int, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
for k := 0; k < len(b); k++ {
c[i][j] += a[i][k] * b[k][j]
}
}
}
return c
}
func pow(a [][]int, n int) [][]int {
res := [][]int{{1, 1, 0}}
for n > 0 {
if n&1 == 1 {
res = mul(res, a)
}
a = mul(a, a)
n >>= 1
}
return res
}/**
* @param {number} n
* @return {number}
*/
var tribonacci = function (n) {
let a = 0;
let b = 1;
let c = 1;
while (n--) {
let d = a + b + c;
a = b;
b = c;
c = d;
}
return a;
};/**
* @param {number} n
* @return {number}
*/
var tribonacci = function (n) {
if (n === 0) {
return 0;
}
if (n < 3) {
return 1;
}
const a = [
[1, 1, 0],
[1, 0, 1],
[1, 0, 0],
];
return pow(a, n - 3)[0].reduce((a, b) => a + b);
};
function mul(a, b) {
const [m, n] = [a.length, b[0].length];
const c = Array.from({ length: m }, () => Array.from({ length: n }, () => 0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
for (let k = 0; k < b.length; ++k) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
return c;
}
function pow(a, n) {
let res = [[1, 1, 0]];
while (n) {
if (n & 1) {
res = mul(res, a);
}
a = mul(a, a);
n >>= 1;
}
return res;
}function tribonacci(n: number): number {
if (n === 0) {
return 0;
}
if (n < 3) {
return 1;
}
const a = [
[1, 1, 0],
[1, 0, 1],
[1, 0, 0],
];
return pow(a, n - 3)[0].reduce((a, b) => a + b);
}
function mul(a: number[][], b: number[][]): number[][] {
const [m, n] = [a.length, b[0].length];
const c = Array.from({ length: m }, () => Array.from({ length: n }, () => 0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
for (let k = 0; k < b.length; ++k) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
return c;
}
function pow(a: number[][], n: number): number[][] {
let res = [[1, 1, 0]];
while (n) {
if (n & 1) {
res = mul(res, a);
}
a = mul(a, a);
n >>= 1;
}
return res;
}class Solution {
/**
* @param Integer $n
* @return Integer
*/
function tribonacci($n) {
if ($n == 0) {
return 0;
} elseif ($n == 1 || $n == 2) {
return 1;
}
$dp = [0, 1, 1];
for ($i = 3; $i <= $n; $i++) {
$dp[$i] = $dp[$i - 1] + $dp[$i - 2] + $dp[$i - 3];
}
return $dp[$n];
}
}