1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <bits/stdc++.h>
using namespace std;
const int LEN = 1e6 + 10;
int n, prefix[LEN], dp[LEN];
int main()
{
cin >> n;
dp[0] = 1, prefix[0] = 1;
for (int i = 1; i <= n; ++i)
{
dp[i] = (prefix[i - 1] + (i < 3 ? 0 : prefix[i - 3])) % 10000;
prefix[i] = (prefix[i - 1] + dp[i]) % 10000;
}
cout << dp[n];
return 0;
}
|