斐波那契是我见过最神奇的东西

#include <bits/stdc++.h>
using namespace std;
char sum[1200];
int s=0,m=0,n;
int main()
{
    cin>>n;
    string s1,s2;
    int a[1200],b[1200];
    int he,i;
    s1="0";
    s2="1";
    for(m=2;m<n+1;m++)
    {
        memset(a,0,sizeof a);
        memset(b,0,sizeof b);
        a[0]=s1.length();
        for(i=1;i<=a[0];i++)
        {
            a[i]=s1[a[0]-i]-'0';
        }
        b[0]=s2.length();
        for(i=1;i<=b[0];i++)
        {
            b[i]=s2[b[0]-i]-'0';
        }
        he=(a[0]>b[0]?a[0]:b[0]);
        for(i=1;i<=he;i++)
        {
            a[i]+=b[i];
            a[i+1]+=a[i]/10;
            a[i]%=10;
        }
        he++;
        while((a[he]==0)&&(he>1))
        he--;
            for(i=he,s=0;i>=1;i--,s++)
            {
                sum[s]=a[i]+'0';
            }
        s1=s2;
        s2=sum;
    }
    cout<<s2<<endl;
    return 0;
}

#include<cstdio>
#include<map>
using namespace tsd;
typedef long long ll;
const int M=1e9+7;//取模 
map<ll,ll>a； 
ll g(ll x)  { return x*x%M; }//平方 
ll f(ll x){
	if(x==1||x==2)	a[x]=1;//边界 
	if(!a[x])//记忆化保存 
		if(x&1)	a[x]=g(f(x+1>>1))+g(f(x-1>>1));//x为奇数 
		else a[x]=g(f(x>>1))+2*f(x>>1)*f((x>>1)-1);//x为偶数 
	return a[x]%M;
}
int main(){
	LL n;
	scanf("%lld",&n);
	printf("%lld",f(n));
	return 1;
}