记录编号	266560	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]生成树计数	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.220 s
提交时间	2016-06-08 07:28:09	内存使用	2.72 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
const int maxn=200;
const int mod=65521;
struct Matrix{
	long long mat[maxn][maxn];
	int r,c;
	Matrix(int r_=0,int c_=0,int on=0){
		memset(mat,0,sizeof(mat));
		r=r_;c=c_;
		if(on)for(int i=1;i<=r;i++)mat[i][i]=1;
	}
	Matrix operator *(Matrix a){
		Matrix ret(r,a.c);
		long long l;
		for(int i=1;i<=r;i++)
			for(int k=1;k<=c;k++){
				l=mat[i][k];
				for(int j=1;j<=a.c;j++)
					(ret.mat[i][j]+=(l*a.mat[k][j])%mod)%=mod;
			}
		return ret;			
	}
	Matrix operator ^(long long k){
		Matrix ret(r,c,1),x(r,c);
		for(int i=1;i<=r;i++)
			for(int j=1;j<=c;j++)
				x.mat[i][j]=mat[i][j];
		while(k){
			if(k&1)
				ret=ret*x;
			k>>=1;
			x=x*x;
		}
		return ret;
	}
}A,B;
 
long long n;
map<int,int>ID;
map<int,bool>used;
int k,e,e1,E[maxn][2];
int cnt,st[1<<17],mem[1<<17];
int fa[maxn],sz[maxn],vis[maxn];
int Find(int x){
	return x==fa[x]?x:fa[x]=Find(fa[x]);
}
bool Check(int s){
	for(int i=1;i<maxn;i++)
		fa[i]=i,sz[i]=1;
	for(int i=0;i<e+e1;i++)
		if(s&(1<<i)){
			int u=Find(E[i][0]),v=Find(E[i][1]);
			if(u!=v){fa[u]=v;sz[v]+=sz[u];}
			else return false;
		}	
	return true;		
}
 
void Solve(int x){
	for(int i=1;i<=x;i++)
		for(int j=i+1;j<=x;j++)
			E[e][0]=i,E[e][1]=j,e++;
	for(int i=1;i<=x;i++)
		E[e+e1][0]=i,E[e+e1][1]=x+1,e1++;
	
	for(int s=(1<<e)-1,num;s>=0;s--)
		if(Check(s)){
			memset(vis,0,sizeof(vis));num=0;
			for(int i=1;i<=x;i++){
				if(vis[Find(i)])continue;
				vis[Find(i)]=++num;
			}
			num=0;
			for(int i=1;i<=x;i++)
				num=num*10+vis[Find(i)];
			if(ID[num])B.mat[ID[num]][1]+=1;
			else{
				A.r+=1;A.c+=1;B.r+=1;
				B.mat[ID[num]=B.r][1]=1;
				st[++cnt]=s;mem[cnt]=num;
			}
		}
	
	for(int t=1,s;t<=cnt;t++){	
		for(int p=(1<<e1)-1,num;p>=0;p--){
			s=st[t]^(p<<e);
			if(Check(s)&&sz[Find(1)]!=1){
				memset(vis,0,sizeof(vis));num=0;
				for(int i=2;i<=x+1;i++){
					if(vis[Find(i)])continue;
					vis[Find(i)]=++num;
				}
				num=0;
				for(int i=2;i<=x+1;i++)
					num=num*10+vis[Find(i)];
				A.mat[ID[num]][ID[mem[t]]]+=1;
			}
		}
	}
	return;
}
  
int main(){
#ifndef ONLINE_JUDGE
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
#endif
	scanf("%d%lld",&k,&n);
	k=min(1ll*k,n);Solve(k);B.c=1;
	A=A^((n-k)%(1ll*(mod+1)*(mod-1)));B=A*B; 
	printf("%lld\n",B.mat[1][1]);
	return 0;
}