思路:
从前向后考虑每一个点,不难发现每个点只能向它的前\(k\)个点连边.
因此我们维护一下最后\(k\)个点的连通性,然后做状压dp.
我们用最小表示法来表示\(k\)个点的连通性,比如12123这种形式,相同的数字表示在相同集合中.
然后我们就枚举一下第\(k+1\)个点如何向前\(k\)个点连边.
注意:合法的连边不能出现环,同时还要保证第\(1\)个点不能被孤立.
然后就有了一个转移矩阵,就可以跑矩乘了.
注意每个状态的初始方案并不是一,而是每个每个连通图的所有生成树的方案之积.
而由Prufer序列可得\(n\)个点的生成树总数为\(n^{n-2}\).
至此应该没有什么问题了(除了代码实现).
#include<map>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
long long n;int k;
int lim;
int cnt,seq[110][10],now[10],vis[10];
void dfs(int dep){
if(dep==k+1){
memset(vis,0,sizeof vis);
for(int i=1;i<=k;++i)if(!vis[now[i]])vis[now[i]]=i;
for(int i=1;i<=lim;++i)if(!vis[i])return;
for(int i=1;i<=lim;++i)for(int j=i+1;j<=lim;++j)if(vis[i]>vis[j])return;
++cnt;for(int i=1;i<=k;++i)seq[cnt][i]=now[i];
return;
}
for(int i=1;i<=lim;++i)now[dep]=i,dfs(dep+1);
}
#define Min(x,y) ((x)<(y)?(x):(x))
inline int calc(int d){
int mi=1,re=0;
for(int i=1;i<=k;++i)re+=mi*seq[d][i],mi*=10;
return re;
}
map<int,int>M;
static const int mod=65521;
inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}
struct Matrix{
int w,h,d[110][110];
Matrix(int _w,int _h):w(_w),h(_h){memset(d,0,sizeof d);}
inline void operator*=(const Matrix&B){
Matrix C(w,B.h);
for(int i=1;i<=C.w;++i)for(int j=1;j<=C.h;++j)
for(int k=1;k<=h;++k)inc(C.d[i][j],(long long)d[i][k]*B.d[k][j]%mod);
*this=C;
}
};
int pre[10],pa[10],nowseq[10];
inline int find(int p[],int x){return x==p[x]?x:p[x]=find(p,p[x]);}
inline void merge(int p[],int x,int y){p[find(p,x)]=find(p,y);}
const int get[]={1,1,1,3,16,125};
int main(){
scanf("%d%lld",&k,&n),k=Min(k,n-1);register int i,j;
for(i=1;i<=k;++i){
lim=i,dfs(1);
}
Matrix ans(1,cnt);
for(i=1;i<=cnt;++i){
ans.d[1][i]=1;
for(j=1;j<=k;++j){int count=0;for(int q=1;q<=k;++q)if(seq[i][q]==j)++count;ans.d[1][i]*=get[count];}
M[calc(i)]=i;
}
Matrix add(cnt,cnt);
for(int t=1;t<=cnt;++t){
for(i=1;i<=k+1;++i)pre[i]=i;
for(i=1;i<=k;++i)for(j=i+1;j<=k;++j)if(seq[t][i]==seq[t][j])merge(pre,i,j);
for(int S=0;S<(1<<k);++S){
memcpy(pa,pre,sizeof pa);
bool can=1;
for(i=0;i<k;++i)if((S>>i)&1){if(find(pa,i+1)==find(pa,k+1))can=0;else merge(pa,i+1,k+1);}
if(!can)continue;
for(i=1;i<=k+1;++i)pa[i]=find(pa,i);
memset(nowseq,0,sizeof nowseq);
int id=0;
for(i=1;i<=k+1;++i){
if(nowseq[i]==0){
++id;
for(j=i;j<=k+1;++j)if(pa[j]==pa[i])nowseq[j]=id;
}
}
bool ok=0;
for(i=2;i<=k+1;++i)if(nowseq[1]==nowseq[i]){ok=1;break;}
if(ok){
memset(nowseq,0,sizeof nowseq);
id=0;
for(i=2;i<=k+1;++i){
if(nowseq[i]==0){
++id;
for(j=i;j<=k+1;++j)if(pa[j]==pa[i])nowseq[j]=id;
}
}
int mi=1,re=0;
for(i=2;i<=k+1;++i)re+=mi*nowseq[i],mi*=10;
if(M[re]==0)puts("WA");
inc(add.d[t][M[re]],1);
}
}
}
n-=k;
for(;n;n>>=1,add*=add)if(n&1)ans*=add;
printf("%d",ans.d[1][1]);
return 0;
}