记录编号	131531	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]生成树计数	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.204 s
提交时间	2014-10-24 16:57:20	内存使用	0.37 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define Mod 65521
#define int64 long long
using namespace std;
int K,Num,fa[52]={0};
int64 N;
vector<int> step;
class Matrix{
	public:
	int64 ele[61][61];
	int n,m;
	void empty(int N,bool zero){n=N;m=N;if(!zero)for(int i=1;i<=n;i++) ele[i][i]=1;}
	Matrix(){memset(ele,0,sizeof(ele));n=0;m=0;}
	Matrix operator*(const Matrix &a){
		Matrix c; c.n=n; c.m=a.m;
		for(int i=1;i<=c.n;i++)
			for(int j=1;j<=c.m;j++)
				for(int k=1;k<=a.m;k++)
					(c.ele[i][j]+=ele[i][k]*a.ele[k][j])%=Mod;
		return c;
	}
}M,D;
int get_num(int w,int t){return (w>>(3*t))&7;}
int change_num(int w,int t,int i){return (w&(~(7<<(3*t))))|(i<<(3*t));}
int find(int* fa,int x){return fa[x]?fa[x]=find(fa,fa[x]):x;}
void packback(int* fa,int k,int w){
	int tp[52]={0};
	for(int i=1;i<=k;i++){
		int t=get_num(w,i);
		if(!tp[t]) tp[t]=i,fa[i]=0; else fa[i]=tp[t];
	}
}
int expand_num(int* fa,int k){
	int tp[52]={0},res=0,color=0;
	for(int i=1;i<=k;i++){
		int t=find(fa,i);
		if(!tp[t]) tp[i]=tp[t]=++color; else tp[i]=tp[t];
	}
	for(int i=1;i<=k;i++) res=change_num(res,i,tp[i]);
	return res;
}
Matrix pow(Matrix a,int64 n){
	Matrix res; res.empty(Num,false);
	for(;n;n>>=1,a=a*a) if(n&1) res=res*a;
	return res;
}
void dfs(int t,int cnt,int w){
	if(t==K) step.push_back(w);
	else{
		for(int i=1;i<=cnt;i++) dfs(t+1,cnt,change_num(w,t+1,i));
		dfs(t+1,cnt+1,change_num(w,t+1,cnt+1));
	}
}
bool check(int* fa,int k,int pos){
	for(int i=1;i<=k;i++){
		if(pos&(1<<(i-1))){
			int t=find(fa,i);
			if(t==find(fa,k+1)) return false; else fa[find(fa,k+1)]=t;
		}
	}return true;
}
void calc_M(int t,int w){
	if(t==K) M.ele[1][lower_bound(step.begin(),step.end(),w)-step.begin()+1]++;
	else{
		int tp[52]={0};packback(tp,t,w);
		for(int i=0;i<(1<<t);i++){
			memmove(fa,tp,sizeof(tp));
			if(check(fa,t,i)) calc_M(t+1,expand_num(fa,t+1));
		}
	}
}
void calc_D(){
	int tp[52];
	for(int i=1;i<=Num;i++){
		int tmp=step[i-1]; packback(tp,K,tmp);
		for(int j=0;j<(1<<K);j++){
			memmove(fa,tp,sizeof(tp));
			if(check(fa,K,j)){
				bool flag=false;
				for(int k=2;k<=K+1;k++){
					if(find(fa,1)==find(fa,k)){
						int t=fa[1];
						for(int l=2;l<=K+1;l++){
							if(fa[l]==1) fa[l-1]=K+1;
							else if(fa[l]>0) fa[l-1]=fa[l]-1;
							else fa[l-1]=0;
						}
						if(t>0) fa[K+1]=t-1; else fa[K+1]=0;
						D.ele[i][lower_bound(step.begin(),step.end(),expand_num(fa,K))-step.begin()+1]++;
						break;
					}
				}
			}
		}
	}
}
int main(){
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	cin>>K>>N;
	step.clear(); dfs(0,0,0);
	sort(step.begin(),step.end());
	Num=step.size();
	M.n=1; M.m=Num; D.n=Num; D.m=Num;
	calc_M(0,0); calc_D();
	M=M*pow(D,N-K);
	cout<<M.ele[1][1]<<endl;
}