\(30pts\)

我会递归。

很显然，我们可以将肥波纳气数列看做一个函数处理：

\(f(x) = \begin{cases}
f(x - 1) + f(x - 2) + f(x - 3) & x \geq 3 \cr
0 & x = 0 \cr
1 & x \in \{1, 2\}
\end{cases}\)

故我们可以进行递归求解：

long long f(long long x) {
    if (x == 0) return 0;
    if (x <= 2) return 1;
    return f(x - 1) + f(x - 2) + f(x - 3);
}

当然，你可以记忆化（虽然没啥用）：

long long F[N];

long long f(long long x) {
    if (F[x]) return F[x];
    if (x == 0) return 0;
    if (x <= 2) return 1;
    return F[x] = f(x - 1) + f(x - 2) + f(x - 3);
}

时间复杂度 \(O(2^n)\)

\(60pts\)

我会递推。

题目中已经给出了公式，那么我们便可以考虑预处理所有的 \(F_i\) 值，然后再以线性的复杂度输出：

long long F[N];

void prepare() {
    F[0] = 0, F[1] = F[2] = 1;
    for (int i = 1; i < N; i++)
        F[i] = F[i - 1] + F[i - 2] + F[i - 3];
}

时间复杂度 \(O(n)\)

\(100pts\)

考虑矩阵加速。

令 \(F_i = \begin{pmatrix}
f_i \cr
f_{i - 1} \cr
f_{i - 2}
\end{pmatrix}
\)。

于是对于 \(f_n\) 的值我们只需要计算 \(F_n\) 即可。

那我们怎么求 \(F_n\) 呢？

我们令矩阵 \(A\)，使得 \(F_i \times A = F_{i + 1}\)。

于是有 \(F_n = F_1 \times A^n\)。

现在我们来求矩阵 \(A\) 到底是啥。

假设 \(A = \begin{pmatrix}
a & b & c \cr
d & e & f \cr
g & h & i
\end{pmatrix}
\)，那么，由 \(F_i \times A = F_{i + 1}\) 可得：

\(\begin{cases}
f_i \times a + f_{i - 1} \times d + f_{i - 2} \times g = f_{i +1} \cr
f_i \times b + f_{i - 1} \times e + f_{i - 2} \times h = f_i \cr
f_i \times c + f_{i - 1} \times f + f_{i - 2} \times i = f_{i - 1}\cr
f_{i + 1} = f_i + f_{i - 1} + f_{i - 2}
\end{cases}\)

解得 \(\begin{cases}
a = 1 \cr
b = 1 \cr
c = 0 \cr
d = 1 \cr
e = 0 \cr
f = 1 \cr
g = 1 \cr
h = 0 \cr
i = 0
\end{cases}
\Longrightarrow
A = \begin{pmatrix}
1 & 1 & 0 \cr
1 & 0 & 1 \cr
1 & 0 & 0
\end{pmatrix}\)

时间复杂度 \(O(\log n)\)

提供std

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

struct matrix {
    ll n, m;
    ll a[4][4];
    
    matrix() {
        n = m = 0;
        memset(a, 0, sizeof(a));
    }
    
    friend matrix operator * (const matrix x, const matrix &y) {
        matrix ans;
        ans.n = x.n, ans.m = y.m;
        for (int i = 1; i <= x.n; i++)
            for (int j = 1; j <= y.m; j++)
                for (int k = 1; k <= x.m; k++)
                    (ans.a[i][j] += x.a[i][k] * y.a[k][j]) %= mod;
        return ans;
    }
};

matrix mul(matrix a, ll b) {
    matrix F;
    F.n = 1, F.m = 3;
    F.a[1][1] = 2, F.a[1][2] = F.a[1][3] = 1;
    while (b) {
        if (b & 1) F = F * a;
        a = a * a;
        b >>= 1;
    }
    return F;
}

ll n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> n;
    
    if (n <= 3) {
        cout << (n == 0 ? 0 : (n == 3 ? 2 : 1)) << '\n';
        return 0;
    }
    
    matrix A;
    A.n = A.m = 3;
    A.a[1][1] = A.a[1][2] = A.a[2][1] = A.a[2][3] = A.a[3][1] = 1;
    
    cout << mul(A, n - 3).a[1][1] << '\n';
    return 0;
}