22 lines
425 B
C++
22 lines
425 B
C++
// lanqiao 2110 (积木画)
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 10000010, MOD = 1e9 + 7;
|
|
int f[N];
|
|
/*
|
|
递推法:
|
|
f1=1 f2=2 f3=5 f4=11 f5=24 f6=53
|
|
f[n] = 2*f[n-1] + f[n-3]
|
|
*/
|
|
int main(){
|
|
int n; cin >> n;
|
|
f[1] = 1, f[2] = 2; f[3] = 5;
|
|
for(int i = 4; i <= n; i++){
|
|
f[i] = (2*f[n-1] % MOD + f[i-3] % MOD) % MOD;
|
|
}
|
|
cout << f[n] << endl;
|
|
return 0;
|
|
}
|
|
/* test samples -> 5
|
|
3
|
|
*/ |