递推+高精

 

 

/**************************************************************
    Problem: 1002
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:28 ms
    Memory:1256 kb
****************************************************************/
 
/*
    强行找规律题
    f1=1   f2=3
    然后是斐波拉契数列
    n为奇数 的时候就是 fn*fn
    否则就是 fn*fn-4
    至于证明不知道。。 
*/
#include<cstdio>
#define max(a,b) ((a>b)?(a):(b))
using namespace std;
const int N=1e3+50;
struct Gj
{
    int m[N];
    Gj operator = (int x)
    {
        for(int i=1;i<=1000;i++) m[i]=0;
        m[0]=1;m[1]=x;
        return *this;
    }
    Gj operator * (Gj b)
    {
        Gj a=*this,c;c=0;
        for(int i=1;i<=a.m[0];i++)
        for(int j=1;j<=b.m[0];j++)
        {
            c.m[i+j-1]+=a.m[i]*b.m[j];
            int k=c.m[i+j-1]/10;
            c.m[i+j-1]%=10;
            c.m[i+j]+=k;
        }
        c.m[0]=a.m[0]+b.m[0];
        while(c.m[c.m[0]]==0) c.m[0]--;
        return c;
    }
    Gj operator + (Gj b)
    {
        Gj a=*this,c;c=0;
        int l=max(a.m[0],b.m[0])+1;
        for(int i=1;i<=l;i++)
        {
            c.m[i]+=a.m[i]+b.m[i];
            int k=c.m[i]/10;
            c.m[i]%=10;
            c.m[i+1]+=k;
        }
        c.m[0]=l+1;
        while(c.m[c.m[0]]==0) c.m[0]--;
        return c;
    }
    Gj operator - (int x)
    {
        Gj a=*this;
        for(int i=1;i<=a.m[0];i++)
        {
            if(a.m[i]>=x)
            {
                a.m[i]-=x;break;
            }
            a.m[i]+=(10-x); x=1;
        }
        while(a.m[a.m[0]]==0) a.m[0]--;
        return a;
    }
}f[105],res;
void print(Gj a)
{
    for(int i=a.m[0];i>=1;i--) printf("%d",a.m[i]);
    printf("\n");
}
int main()
{
    int n;
    scanf("%d",&n);
    if(n==1) {printf("1\n");return 0;} 
    if(n==2) {printf("5\n");return 0;} 
    f[1]=1;f[2]=3;
    for(int i=3;i<=n;i++)
    {
        f[i]=f[i-2]+f[i-1];
    }
//  print(f[n]);
    if(n&1) res=f[n]*f[n];
    else res=f[n]*f[n],res=res-4;
    print(res);
    return 0;
}