题解 | 小红蹦跳蹦跳

//(a+b)modP=[(amodP)+(bmodP)]modP
//(a×b)modP=[(amodP)×(bmodP)]modP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int P=1e9+7;
void solve() {
    int n;cin>>n;
    vector<int>dpl(n+1,0),dpr(n+1,0);
    dpl[1]=1;dpr[1]=0;dpl[2]=0;dpr[2]=1;
    for(int i=3;i<=n;i++){
        dpl[i]=(dpr[i-1]+dpl[i-2])%P;
        dpr[i]=(dpr[i-2]+dpl[i-2])%P;
    }
    int ans=(dpl[n]+dpr[n])%P;
    cout<<ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}
// 64 位输出请用 printf("%lld")