#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010000,mod=1000000007;
long long f[N];
int main()
{
f[0]=1,f[1]=1,f[2]=2,f[3]=5;
for(int i=4;i<=N;i++)
{
f[i]=2*f[i-1]+f[i-3];
f[i]%=mod;
}
int n;
cin>>n;
cout<<f[n]<<endl;
}
写的很好,代码量也很少
纠正一下,最后的转移方程前一步应该是加到f0
重新发一遍