今天带来一道第 N 个泰波那契数，题不难，但是我们可以从中学习到一些方法。

首先是使用动态规划来解决，题目本身的描述就把状态方程告诉你了，直接如题就能得到代码：

class Solution {
public:
    int tribonacci(int n) {
        int dp[38];
        dp[0] = 0, dp[1] = 1, dp[2] = 1;
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }
};

但这个方法当n很大的话，o(n)的复杂度好像就不够用了，那么此时就提出一种叫矩阵快速幂的方法。

为了了解矩阵快速幂，先来了解一下什么是快速幂，在求一个数的幂时，比如a的n次方，我们如果每次乘n就很慢，那么我们就可以把n用二进制表示，例如7会被表示成111，那么$a^7=a^4+a^2+a^1$。我们可以不去计算a的每一个次方而是去计算$a^1,a^2,a^4,a^8,…………$然后在相应二进制为1，原式乘以a。

给出一个快速幂模版：

// 计算 (a^b) % mod
ll fastPow(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod; // 防止初始溢出
    while (b) {
        if (b & 1)
            res = (res * a) % mod; // 若当前位为1，累乘
        a = (a * a) % mod;         // 底数平方
        b >>= 1;                   // 指数右移一位
    }
    return res;
}

那么该题显然不是纯粹的幂求解，连是不是幂求解一眼也看不出来。我们先根据题目描述构建一个答案矩阵$\begin{bmatrix} T_{0} & T_{1}& T_{2} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$，那么我们如何得到结果矩阵$\begin{bmatrix} T_{n-2} & T_{n-1}& T_{n} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$，因为已知$T_{n+3}=T_{n+2}+T_{n+1}+T_{n}$，所以结果矩阵为$\begin{bmatrix} T_{n-2} & T_{n-1}& T_{n+2}+T_{n+1}+T_{n} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$，它由$\begin{bmatrix} T_{0} & T_{1}& T_{2} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$与$\begin{bmatrix} 0& 0& 1 \\ 1 & 0 & 1\\ 0 & 1 & 1 \end{bmatrix}^{n-2}$做矩阵乘法得到，这样求解的方法就叫矩阵快速幂。

那么就根据这个写一下代码：

class Solution {
public:
    vector<vector<long long>> mul(vector<vector<long long>>& m, vector<vector<long long>>& n) {
        vector<vector<long long>> mar(3, vector<long long>(3, 0));
        for (int i = 0; i < m.size(); ++i) {
            for (int j = 0; j < n[0].size(); ++j) {
                mar[i][j] =
                    n[0][j] * m[i][0] + n[1][j] * m[i][1] + n[2][j] * m[i][2];
            }
        }
        return mar;
    }
    int tribonacci(int n) {
        vector<vector<long long>> mar = {{0, 1, 1}, {0, 0, 0}, {0, 0, 0}};
        vector<vector<long long>> a = {{0, 0, 1}, {1, 0, 1}, {0, 1, 1}};
        if (n > 2) {
            n = n - 2;
            while (n > 0) {
                if (n & 1) {
                    mar = mul(mar, a);
                }
                a = mul(a, a);
                n = n >> 1;
            }
        } else {
            return mar[0][n];
        }
        return mar[0][2];
    }
};

这样子算法的时间复杂度就来到了$O（\log_2 n）$，大大加快了时间，虽然本题并不能体现出快速幂的价值，但是快速幂是一个值得掌握的方法。