题目链接:
#include <bits/stdc++.h>using namespace std;
using i64 = long long;const int N = 1e6 + 10;
int f[N], pre[N];int main()
{ios::sync_with_stdio(false), cin.tie(nullptr);int n;cin >> n;pre[0] = f[0] = 1;for (int i = 1; i <= n; i++) {f[i] = (i64)((i >= 1 ? pre[i - 1] : 0) + (i >= 3 ? pre[i - 3] : 0)) % 10000;pre[i] = (i64)(pre[i - 1] + f[i]) % 10000;}cout << f[n];return 0;
}