发现5个点的联通情况仅52种，因此状压：令f[i][j]表示前i个点满足：1.前i-k个点是树；2.最后k个点连通性为j的方案数；3.最后k个点到前i-k个点有边，转移用矩阵乘法：暴力求出A[i][j]表示（连通性）从状态i转移到j的方案数，快速幂一下即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define mod 65521
 5 int m,t,ans,a[11],v[11],b[61][11],f[61];
 6 ll n;
 7 struct ji{
 8     int a[61][61];
 9     ji operator *(const ji &b)const{
10         ji c;
11         for(int i=1;i<=t;i++)
12             for(int j=1;j<=t;j++){
13                 c.a[i][j]=0;
14                 for(int k=1;k<=t;k++)
15                     c.a[i][j]=(c.a[i][j]+1LL*a[i][k]*b.a[k][j])%mod;
16             }
17         return c;
18     }
19 }A;
20 void dfs(int k,int s){
21     if (k>m){
22         memcpy(b[++t],a,sizeof(a));
23         f[t]=1;
24         for(int i=1;i<=m;i++){
25             int s=0;
26             for(int j=1;j<=m;j++)
27                 if (a[j]==i)s++;
28             for(int j=1;j<=s-2;j++)f[t]=f[t]*s;
29         }
30         return;
31     }
32     for(int i=1;i<=s;i++){
33         a[k]=i;
34         dfs(k+1,s+(i==s));
35     }
36 }
37 int find(){
38     memset(v,0,sizeof(v));
39     for(int i=1;i<=m;i++){
40         if (!v[a[i]])v[a[i]]=++v[0];
41         a[i]=v[a[i]];
42     }
43     for(int i=1;i<=t;i++){
44         bool p=0;
45         for(int j=1;j<=m;j++)
46             if (b[i][j]!=a[j])p=1;
47         if (!p)return i;
48     }
49 }
50 void dfs(int k,int s,int p){
51     if (k>m){
52         for(int i=2;i<=m;i++)
53             if (s&(1<<b[p][i]-1))a[i-1]=m+1;
54             else a[i-1]=b[p][i];
55         a[m]=m+1;
56         A.a[p][find()]++;
57         return;
58     }
59     dfs(k+1,s,p);
60     if (!(s&(1<<b[p][k]-1)))dfs(k+1,s+(1<<b[p][k]-1),p);
61 }
62 ji ksm(ji n,ll m){
63     if (m==1)return n;
64     ji s=ksm(n,m>>1);
65     s=s*s;
66     if (m&1)s=s*n;
67     return s;
68 }
69 int main(){
70     scanf("%d%lld",&m,&n);
71     dfs(1,1);
72     for(int i=1;i<=t;i++){
73         bool p=1;
74         for(int j=2;j<=m;j++)
75             if (b[i][j]==1)p=0;
76         dfs(p+1,p,i);
77     }
78     A=ksm(A,n-m+(n==m));
79     for(int i=1;i<=t;i++)ans=(ans+1LL*A.a[i][1]*f[i])%mod;
80     printf("%d",ans);
81 }

View Code