记录编号	288697	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]生成树计数	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.199 s
提交时间	2016-08-03 14:15:52	内存使用	0.38 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
const int p=65521;
long long n;
int k,i,j,l,cnt;
struct matrix{
	long long a[52][52];
	void operator *= (const matrix x){
		matrix ans={0};
		for (int i=0;i<cnt;i++)
		for (int j=0;j<cnt;j++)
		for (int k=0;k<cnt;k++)
			ans.a[i][j]=(ans.a[i][j]+a[i][k]*x.a[k][j])%p;
		*this=ans;
	}
	void print(){
		for (int i=0;i<cnt;i++){
			for (int j=0;j<cnt;j++)
			printf("%lld ",a[i][j]);
			puts("");
		}
		puts("");
	}
}x,ans,now;
matrix mi(matrix x,long long y){
	matrix ans=x;y--;
	while (y){
		if (y&1) ans*=x;
		x*=x;y/=2;
	}
	return ans;
}
bool sit[52][5][5],hash[5][5];
int num;
bool check(int num,int x,int y){
	int ans=0;
	while (!sit[num][ans][x]) ans++;
	return sit[num][ans][y];
}
int find(int num,int x){
	int ans=0;
	while (!sit[num][ans][x]) ans++;
	return ans;
}
int size(int num,int x){
	int ans=0;
	for (int i=0;i<k;i++) ans+=sit[num][x][i];
	return ans;
}
void dfs(int x){
	if (x==k){
		memcpy(sit[cnt++],hash,sizeof hash);return;
	}
	hash[num++][x]=1;
	dfs(x+1);
	hash[--num][x]=0;
	for (int i=0;i<num;i++){
		hash[i][x]=1;dfs(x+1);hash[i][x]=0;
	}
}
int main()
{
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	cin>>k>>n;
	dfs(0);
	/*printf("%d\n",cnt);
	for (i=0;i<cnt;i++){
		printf("\nsit[%d]=\n",i);
		for (j=0;j<k;j++){
			for (l=0;l<k;l++)
			if (sit[i][j][l]) printf("%d ",l+1);
			puts("");
		}
	}*/
	for (i=0;i<cnt;i++){
		now.a[0][i]=1;
		for (j=0;j<k;j++){
			int c=0;
			for (l=0;l<k;l++) c+=sit[i][j][l];
			if (c<=2) continue;
			c=pow(c,c-2);
			now.a[0][i]*=c;
		}
		for (j=1;j<cnt;j++) now.a[j][i]=now.a[0][i];
	}
	for (i=0;i<cnt;i++)
	for (j=0;j<cnt;j++){
		bool vis[5]={0};
		for (int a=1;a<k;a++)
		for (int b=1;b<k;b++)
		if (check(i,a,b)&&!check(j,a-1,b-1)) goto end;
		for (int a=1;a<k;a++)
		for (int b=1;b<k;b++){
			if (!check(i,a,b)&&check(j,a-1,b-1))
			if (!check(j,a-1,k-1)||!check(j,b-1,k-1))
				goto end;
		} 
		x.a[i][j]=1;
		for (int a=0;a<k-1;a++)
		if (check(j,a,k-1)){
			int fic=find(i,a+1);
			if (vis[fic]) continue;
			vis[fic]=1;
			x.a[i][j]*=size(i,fic);
		}
		end:;
	}
	//x.print();now.print();
	ans=now;ans*=mi(x,n-k);
	cout<<ans.a[0][cnt-1]<<endl;
	return 0;
}