Luogu

分析

打表找规律：

n=1 ans=1
n=2 ans=5
n=3 ans=16
n=4 算不出

那就分析前三项，发现：

$1=1\times 1,5=3\times 3-4,16=4\times 4,...$

看样子是平方数，不过好像有变化——偶数项要减4。

然后要平方的数是可以递推的，$f[1]=1,f[2]=3,f[i]=f[i-2]+f[i-1](i>2)$。

到此递推式已经明显了，不过有一个小技巧：只推底数，然后处理最后一项即可。

加上高精即可AC。

另外矩阵树定理也是可以做的。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
class BigInteger //以下为高精度模板
{ 
    public:
    int size,num[1000];
    BigInteger()
    {
        size=0;
        memset(num,0,sizeof(num));
    }
    BigInteger(int data)
    {
        size=0;
        while (data!=0)
        {
            size++;
            num[size]=data%10;
            data=data/10;
        }
    }
    void init(int data)
    {
        size=0;
        while (data!=0)
        {
            size++;
            num[size]=data%10;
            data=data/10;
        }
    }
};
BigInteger operator +(BigInteger a,BigInteger b)
{
    BigInteger c;
    int s=max(a.size,b.size);
    c.size=s;
    for (int i=1;i<=s;i++)
        c.num[i]=a.num[i]+b.num[i];
    for (int i=1;i<=s;i++)
        if (c.num[i]>=10)
        {
            c.num[i+1]+=c.num[i]/10;
            c.num[i]=c.num[i]%10;
        }
    if (c.num[s+1]!=0) c.size++;
    return c;
}
BigInteger operator -(BigInteger a,BigInteger b)
{
    BigInteger c;
    int s=max(a.size,b.size);
    c.size=s;
    for (int i=1;i<=s;i++)
        c.num[i]=a.num[i]-b.num[i];
    for (int i=1;i<=s;i++)
        if (c.num[i]<0)
        {
            c.num[i+1]-=c.num[i]/10;
            c.num[i]=c.num[i]%10;
        }
    if (c.num[s+1]!=0) c.size++;
    return c;
}
BigInteger operator *(BigInteger a,BigInteger b)
{
    BigInteger c;
    int s1=a.size,s2=b.size;
    for (int i=1;i<=s1;i++)
        for (int j=1;j<=s2;j++)
            c.num[i+j-1]+=a.num[i]*b.num[j];
    int s=s1+s2-1;
    int k=1;
    while ((c.num[k]!=0)||(k<=s))
    {
        c.num[k+1]+=c.num[k]/10;
        c.num[k]=c.num[k]%10;
        k++;
    }
    if (c.num[k]==0) k--;
    c.size=k;
    return c;
}
ostream& operator <<(ostream &out,BigInteger a)
{
    int s=a.size;
    for (int i=s;i>=1;i--) out<<a.num[i];
    return out;
}
BigInteger f[1010],ans;
int main()
{
    f[1].init(1); f[2].init(3); 
    int n; scanf("%d",&n);
    for (int i=3;i<=n;i++) f[i]=f[i-1]+f[i-2]; //递推
    if (n%2==1) ans=f[n]*f[n]; //奇数项则平方
    else ans=f[n]*f[n]-4; //偶数项则平方减4
    cout<<ans<<endl; //输出
    return 0;
}