21 lines
424 B
C++
21 lines
424 B
C++
#include<bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
const int N = 1000010;
|
|
int f[N], n;
|
|
const int MOD = 10000;
|
|
|
|
int main() {
|
|
//手工计算出前三个初始值
|
|
f[0] = 1;
|
|
f[1] = 1;
|
|
f[2] = 2;
|
|
cin >> n;
|
|
for (int i = 3; i <= n; i++) {
|
|
//每一步都要取模
|
|
f[i] = (f[i - 1] * 2) % MOD + f[i - 3] % MOD;
|
|
f[i] %= MOD;
|
|
}
|
|
printf("%d\n", f[n]);
|
|
return 0;
|
|
} |