题意
一个n个点的树,点i只能向[i−k,i−1]内的点连边,求有标号生成树的个数
然而做法，好吧我也不知道这是什么做法，所以有些注释大部分注释所有注释我都写在了代码里面，大佬们就自己去看看吧
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define RG register
#define MOD 65521
#define MAX 55
inline ll read()
{
RG ll x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
ll n;int K,cnt;
int p[1<<20],st[MAX];
struct Matrix
{
int s[MAX][MAX];
void clear(){memset(s,0,sizeof(s));}
void init(){clear();for(int i=1;i<=cnt;++i)s[i][i]=1;}
}G;
Matrix operator*(Matrix a,Matrix b)
{
Matrix ret;ret.clear();
for(int i=1;i<=cnt;++i)
for(int j=1;j<=cnt;++j)
for(int k=1;k<=cnt;++k)
ret.s[i][j]=(ret.s[i][j]+1ll*a.s[i][k]*b.s[k][j])%MOD;
return ret;
}
Matrix fpow(Matrix a,ll b)
{
Matrix s;s.init();
while(b){if(b&1)s=s*a;a=a*a;b>>=1;}
return s;
}
bool check(int t)//检查一个状态是否合法
{
int tmp=1<<1;//因为第一个点一定属于一号联通快，所以先把一号联通快放进去检查
for(int i=3;i<K+K+K;i+=3)
{
for(int j=1;j<((t>>i)&7);++j)//检查比当前编号小的所有编号是否都已经出现过
if(!(tmp&(1<<j)))return false;
tmp|=1<<((t>>i)&7);//将当前编号也给放进来
}
return true;
}
void dfs(int x,int t)//暴力找出所有状态，每个编号利用3个二进制位存
{
if(x==K){if(check(t))p[t]=++cnt,st[cnt]=t;return;}
for(int i=1;i<=K;++i)dfs(x+1,t|(i<<(x+x+x)));
}
int fa[MAX],a[MAX];
int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}
int f[MAX],g[MAX][MAX];
int main()
{
K=read();n=read();dfs(1,1);
for(int i=1;i<=cnt;++i)
{
f[i]=1;memset(a,0,sizeof(a));
for(int j=0;j<K;++j)++a[(st[i]>>(j*3))&7];
for(int j=1;j<=K;++j)
if(a[j]==3)f[i]=3;
else if(a[j]==4)f[i]=16;
else if(a[j]==5)f[i]=125;
int t=st[i];
for(int s=0;s<(1<<K);++s)//暴力枚举当前点对于前面几个点的连边状态
{
for(int j=0;j<=K;++j)fa[j]=j;
for(int j=0;j<K;++j)//利用并查集维护联通性
for(int k=j+1;k<K;++k)
if(((t>>(3*j))&7)==((t>>(3*k))&7))
fa[getf(j)]=getf(k);
bool cir=false;
for(int j=0;j<K;++j)//检查当前点的连边
if(s&(1<<j))
{
if(getf(K)==getf(j)){cir=true;break;}//出现了环
fa[getf(K)]=getf(j);
}
if(cir)continue;//连边不合法
for(int j=1;j<=K;++j)//最前面的点必须和后面的一个点联通，否则就无法联通了
if(getf(0)==getf(j)){cir=true;break;}
if(!cir)continue;
int now=0,used=0;
for(int j=0;j<K;++j)//当前存在合法的联通方案，因此当前的状态可以转移到另外的一个状态上去
if(!(now&(7<<(j*3))))//当前点不在任意一个联通块中
{
now|=++used<<(j*3);//新的联通块
for(int k=j+1;k<K;++k)//把所有在一个联通块里的点丢到状态里去
if(getf(j+1)==getf(k+1))
now|=used<<(k*3);
}
g[i][p[now]]++;
}
}
for(int i=1;i<=cnt;++i)
for(int j=1;j<=cnt;++j)
G.s[i][j]=g[i][j];
G=fpow(G,n-K);
int ans=0;
for(int i=1;i<=cnt;++i)
ans=(ans+1ll*G.s[i][1]*f[i])%MOD;
printf("%d
",ans);
return 0;
}
如果有问题的话大佬们可以指出