将原问题转化为求矩阵的幂的问题，然后利用矩阵快速幂求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
typedef long long LL;
class Solution {
 public:
  const int N = 3;
  vector<vector<LL>> mul(vector<vector<LL>>& a, vector<vector<LL>>& b) {
    vector<vector<LL>> c(N, vector<LL>(N));
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j];
      }
    }
    return c;
  }
  int tribonacci(int n) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    vector<vector<LL>> ans = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
    vector<vector<LL>> mat = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};
    int k = n - 2;
    while (k != 0) {
      if ((k & 1) != 0) ans = mul(ans, mat);
      mat = mul(mat, mat);
      k >>= 1;
    }
    return ans[0][0] + ans[0][1];
  }
};