随便摸一发题解算了
打表找规律
前五个答案是1 5 16 45 121
其实是1^2 3^2-4 4^2 7^2-4 11^2
底数就是类似于斐波那契数列,还有偶数项要减4
#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register
using namespace std;
const int N=1e2+10;
il LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
struct Num
{
int w,a[210];
Num(){memset(a,0,sizeof(a)),w=1;}
il void print()
{
++w;
while(w>1&&!a[w]) --w;
for(int i=w;i;--i) printf("%d",a[i]);
}
Num operator + (const Num &bb) const
{
Num an;
an.w=max(w,bb.w);
for(int i=1;i<=an.w;++i) an.a[i]=a[i]+bb.a[i];
for(int i=1;i<=an.w;++i) an.a[i+1]+=an.a[i]/10,an.a[i]%=10;
an.w+=an.a[an.w+1]>0;
return an;
}
Num operator * (const Num &bb) const
{
Num an;
an.w=w+bb.w+1;
for(int i=1;i<=w;++i)
for(int j=1;j<=bb.w;++j)
an.a[i+j-1]+=a[i]*bb.a[j];
for(int i=1;i<=an.w;++i) an.a[i+1]+=an.a[i]/10,an.a[i]%=10;
while(!an.a[an.w]) --an.w;
return an;
}
}a[N];
int n;
int main()
{
n=rd();
a[1].a[1]=1,a[2].a[1]=3;
for(int i=3;i<=n;++i) a[i]=a[i-1]+a[i-2];
a[n]=a[n]*a[n];
if(n%2==0)
{
a[n].a[1]-=4;
for(int i=1;a[n].a[i]<0;++i) --a[n].a[i+1],a[n].a[i]+=10;
}
a[n].print();
return 0;
}
没了?
其实正解是\(Matrix-tree\)
图已经给你了,一个环然后每个点连向中间这个点,这个图的生成树个数就是答案
自己随便搞一下就真没了
然后懒得再写高精了qwq
#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register
using namespace std;
const int N=1e2+10,mod=1e9+7; //诶嘿嘿
il LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
il LL gg(int a[N][N],int n)
{
LL ans=1;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
while(a[j][i])
{
LL x=a[i][i]/a[j][i];
for(int k=i;k<=n;++k) a[i][k]-=a[j][k]*x;
ans=mod-ans;
for(int k=i;k<=n;++k) swap(a[i][k],a[j][k]);
}
for(int i=1;i<=n;++i) ans=(ans*(a[i][i]%mod+mod)%mod)%mod;
return ans;
}
int n,a[N][N];
int main()
{
n=rd();
for(int i=1;i<=n;++i) a[i][i]=3;
a[n+1][n+1]=n;
for(int i=1;i<=n;++i) --a[n+1][i],--a[i][n+1];
for(int i=1;i<n;++i) --a[i][i+1],--a[i+1][i];
--a[1][n],--a[n][1];
printf("%lld\n",gg(a,n));
return 0;
}