题解 | #递归函数的次数#

考察知识点：递归、滚动数组

递归函数调用次数满足递推式 $a_n=a_{n-1}+a_{n-2}+a_{n-3}+1a\_n\; =\; a\_\{n-1\}\; +\; a\_\{n-2\}\; +\; a\_\{n-3\}\; +\; 1$，其中 $a_1=a_2=a_3=1a\_1\; =\; a\_2\; =\; a\_3\; =\; 1$。 由于 $n\le 100,000,000n\; \backslash leq\; 100,000,000$，所以不能直接递归或者迭代求解，考虑使用滚动数组优化。

时间复杂度：$O(n)O(n)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define MOD 1000000

int a[5] = {0, 1, 1, 1};

void solve()
{
    int n;
    cin >> n;
    if (n < 4)
    {
        cout << a[n] << endl;
        return;
    }
    for (int i = 4; i <= n; i++)
    {
        a[4] = (a[1] + a[2] + a[3] + 1) % MOD;
        a[1] = a[2];
        a[2] = a[3];
        a[3] = a[4];
    }
    cout << a[4] << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}