这个题目是黑题,本来想打表的,但是表调不出来(我逊毙了)!
然后随便打了一个递推,凑出了样例,
竟然。
竟然。。
竟然。。。
A了!!!!!!!
直接:(f[i]=f[i-1]*2+f[i-2]~~~f[0]=0,f[1]=1),恭喜你!
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[86]={0,1,2},n,ans,q[800];
/*void search(ll x)
{
if (x<0) return;
if (x==0) {
}
}
void biao()
{
for (int i=3;i<=85;++i)
a[i]=a[i-1]+a[i-2];
for (int i=1;i<=500;++i) {
n=i;
ans=0;
search(i);
cout<<ans<<endl;
}
}*/
int main()
{
// biao();
cin>>n;
ll f[1000010]={0,1};
for (int i=2;i<=n;++i) f[i]=(f[i-1]*2+f[i-2])%1000000007;
cout<<f[n];
return 0;
}