给周围的点编号1到n
我们设f[i]为（1到i和中间点）连成一个联通块的情况数，那么有$f[i]=\sum{f[i-j]*j}$，就是从i-j+1到i里选一个连到中心，然后再把i-j+1到i连成链
但这样的话，1和n不能连，那就再考虑，如果我们通过1-n这条边链起了i个点，那就再从这i个里连1个到中心点，剩下的点连成一个联通块。
这种情况设成g的话，就有$g=\sum{(j-1)*j*f[i-j]}$，其中(j-1)的意思是经过1-n、长度为j的有j-1种情况
然后要写高精度
#include<bits/stdc++.h>
#define pa pair<int,int>
#define ll long long
using namespace std;
const int maxn=,maxs=; ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N;
int f[maxn][maxs],g[maxs],tmp[maxs]; inline void print(int *x){
for(int i=x[];i;i--) printf("%d",x[i]);printf("\n");
} inline void mult(int x,int k){
memset(tmp,,sizeof(tmp));int i;
for(i=;i<=f[x][];i++){
tmp[i]+=f[x][i]*k;
tmp[i+]+=tmp[i]/;tmp[i]%=;
}for(;;i++){if(!tmp[i]){tmp[]=i-;break;}
tmp[i+]+=tmp[i]/;tmp[i]%=;
}
}
inline void add(int x){int i;
for(i=;i<=tmp[];i++){
f[x][i]+=tmp[i];
f[x][i+]+=f[x][i]/;f[x][i]%=;
}for(;;i++){
if(!f[x][i]){f[x][]=max(f[x][],i-);break;}
f[x][i+]+=f[x][i]/;f[x][i]%=;
}
} int main(){
int i,j,k;
N=rd();f[][]=f[][]=;
for(i=;i<=N;i++){
for(j=;j<=i;j++){
mult(i-j,j);add(i);
}
}
for(i=;i<=N;i++){
mult(N-i,(i-)*i);add(N+);
}memcpy(tmp,f[N+],sizeof(tmp));add(N);
print(f[N]);
return ;
}