题目

代码

#include <iostream>
using namespace std;
const long long M = 1e7+10;
const long long MOD = 1e9+7;
long long g[M],f[M];
int main()
{
    f[0] = 1;
    f[1] = 1;
    g[0] = 0;
    g[1] = 2;
    long long N = 0;
    cin>>N;
    for(int i = 2;i<=N;i++)
    {
        g[i] = (g[i - 1] + 2 * f[i - 1]) % MOD;
        f[i] = (f[i - 1] + f[i - 2] + g[i - 2]) %MOD;
    }
    cout<<f[N]<<endl;
    return 0;
}
//        g[i] = (g[i - 1] + 2 * f[i - 1]);
//        f[i] = (f[i - 1] + f[i - 2] + g[i - 2]);