正解：貌似有个叫基尔霍夫矩阵的东西？？？反正我不会

 

非正解：打表找规律（要真是省选，打30分钟的表可以A一道题还是很值的对吧）

 

我们要求一个。。。有N+1个节点的2*N条边的图的生成树的个数，N<=100，那就先打个爆搜？应该有30分吧

 

 1 #pragma GCC optimize(2)
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define int __int128
 7 using namespace std;
 8 inline int read(){
 9     char chr=getchar();    int f=1,ans=0;
10     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
11     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
12     return ans*f;
13 }void write(int x){
14     if(x<0) putchar('-'),x=-x;
15     if(x>9) write(x/10);
16     putchar(x%10+'0');
17 }int n,fa[105],ans,tot;
18 int find(int x){if(fa[x]==x) return x;return find(fa[x]);}//要删除
19 struct P{int x,y;}edge[10001];
20 void dfs(int x,int now){//当前的搜索的边数(x) 已经加入图的边数(now) 
21     if(tot-x+1<n-now-1) return;//可行性剪枝,如果把剩下所有的边都加进去都没有一棵树，则不可能 
22     if(now==n-1) {++ans;return;}
23     dfs(x+1,now);//01搜索，选这条边 
24     int fx=find(edge[x].x),fy=find(edge[x].y);//不选这条边
25     if(fx!=fy){int t=fa[fx]; //显然这里的并查集是要支持删除操作的，不用想太多，不要路径压缩即可 
26         fa[fx]=fy;
27         dfs(x+1,now+1);
28         fa[fx]=t;//删除一次操作，把father变成原来的father
29     }
30 }int f[5005];
31 signed main(){
32     int T=read();
33     for(int kk=1;kk<=T;kk++){
34         n=kk;ans=0;tot=0;
35         for(int i=1;i<=n+10;i++) fa[i]=i;
36         for(int i=1;i<=n-1;i++)    edge[++tot]={i,i+1};edge[++tot]={1,n};
37         for(int i=1;i<=n;i++)   edge[++tot]={n+1,i};++n;//建图加边 
38         dfs(1,0);write(ans);puts("");//搜索输出答案 
39     }
40     return 0;
41 }

让我们来看看它输出了啥：

1

5

16

45
121
320
841
2205
5776
15125
39601
103680
271441
710645
1860496
4870845
12752041
33385280

不难发现 ，n为奇数是，答案是完全平方数，那我们把它们开方出来(只列奇数项)

1

4

11

29

76

199

……

跟斐波那契数列有关（不是1，1，2开头的），自己思考一下，不懂可以看代码

要高精：这里给出主程序部分（高精自己写啊）

如果要高精的万能模板，戳这里（好吧，无耻的赚点分）

 1 signed main()
 2 {
 3     int n;
 4     cin>>n;
 5     if(n==2){cout<<5<<endl;return 0;}
 6     f[1]=4,f[2]=7;
 7     for(int i=3;i<=505;i++) f[i]=f[i-1]+f[i-2];
 8     BigInteger ans=f[n-2];
 9     ans*=ans;
10     if(!(n&1)) ans-=4;
11     cout<<ans;
12     return 0;
13 }