考察知识点:递归、滚动数组
递归函数调用次数满足递推式 ,其中 。 由于 ,所以不能直接递归或者迭代求解,考虑使用滚动数组优化。
时间复杂度:
#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;
}