记忆化搜索！时间复杂度O（logn^2)

记忆化搜索！！！！！！！时间复杂度幂对数遥遥领先！！！！！！
众所不周知：斐波那契数列特性：
1.如果f[i(是偶数)]:f[i]=f[i/2-1]*f[i/2]+f[i/2]+f[i/2+1]
2.如果f[i是奇数]:f[i]=f[(i-1)/2]^2+f[(i+1)/2]2]
由于n较大，如果进行dp,就会把n以下全遍历了，这样就失去了这个特性的意义，仍然过不了。
这个性质的精髓是不用把n以下所有状态都计算了就能算出f[n]
所以我们要用递归！！！
但递归有个缺点——
会重复计算很多状态，
这对这道题是致命的！！！！
然后我们，就有了记忆化搜索——
但是问题又来了！！
数组开不了那么大！！！！！！
但是我们有一个强大的工具——map哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈——map只需要多乘logn的时间即可充当一个无限数组！！！！！
然后此题就过了:
#include <bits/stdc++.h>
using namespace std;
long long k;
map<long long,long long>mp;
long long f(long long n){
k++;
if(n1||n2) return 1;
if(mp[n]!=0) return mp[n];
if(n%2==0){
long long N1=f(n/2)%1000000007;
mp[n]=(f(n/2-1)N1+f(n/2+1)N1%1000000007)%1000000007;
return (f(n/2-1)N1+f(n/2+1)N1%1000000007)%1000000007;
}else{
long long N1=f(n/2);
long long N2=f(n/2+1);
mp[n]=((N1N1)%1000000007+(N2N2)%1000000007)%1000000007;
return ((N1N1)%1000000007+(N2N2)%1000000007)%1000000007;
}
}
int main(){
long long n;
cin>>n;
cout<<f(n)%1000000007;//<<" "<<k;
return 0;
}