记录编号	189137	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]生成树计数	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.059 s
提交时间	2015-09-26 14:15:07	内存使用	0.37 MiB

#include<cstdio>
#include<iostream>
#include<map>
#include<deque>
#include<cstring>
#include<deque>
#include<algorithm>
using namespace std;
typedef long long LL;
const int SIZEC=60,MOD=65521;
LL N;
int K,tot=0;
int P=7;
int Q[210]={0};//所有的合法状态
//用五进制数表示状态
class miku
{
public:
	int n,m;
	LL s[SIZEC][SIZEC];
	void make(int x)
	{
		n=m=x;
		memset(s,0,sizeof(s));
	}
	void ass(int x)
	{
		n=m=x;
		memset(s,0,sizeof(s));
		for(int i=1;i<=x;i++)
			s[i][i]=1;
	}
	void print()
	{
		cout<<n<<" "<<m<<endl;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
				cout<<s[i][j]<<" ";
			cout<<endl;
		}
		cout<<endl;
	}
};
miku T;
miku A;//转移矩阵
inline miku operator *(miku a,miku b)
{
	miku c;
	c.make(0);
	c.n=a.n,c.m=b.m;
	for(int i=1;i<=a.n;i++)
		for(int j=1;j<=b.m;j++)
		{
			for(int k=1;k<=b.n;k++)
				c.s[i][j]+=a.s[i][k]*b.s[k][j];
			c.s[i][j]%=MOD;
		}
	return c;
}
miku quickpow(miku a,LL t)
{
	miku c;
	c.ass(a.n);
	while(t)
	{
		if(t&1) c=c*a;
		a=a*a;t>>=1;
	}
	return c;
}
int get(int x,int id){return (x>>(id-1)*3)&P;}
int changedig(int x,int j,int t)//把x的第j为改成t
{
	int tem=x>>(j-1)*3;
	x-=tem<<(j-1)*3;tem>>=3;x+=tem<<j*3;x+=t<<(j-1)*3;
	return x;
}
int get_sum(int x,int j)
{
	int re=0;
	for(int i=K;i>=1;i--) if(get(x,i)==j) re++;
	return re;
}
int small(int x)//将x最小表示
{
	int P[7]={0},cnt=0;
	int re=0;
	for(int i=K;i>=1;i--)
	{
		int tem=get(x,i);
		if(P[tem]==0&&tem!=0) P[tem]=++cnt;
		re=(re<<3)+P[tem];
	}
	return re;
}
int change_A(int x,int last,int then)
{
	for(int i=K;i>=1;i--)
	{
		if(get(x,i)==last) x=changedig(x,i,then);
	}
	return x;
}
int find_Q(int x)
{
	for(int i=1;i<=tot;i++)
		if(Q[i]==x) 
			return i;
	return 0;
}
int make(int x,int y,int now)//将i以y的方式接在x的尾部
{
	bool h[7]={0};
	int tem=6;
	for(int i=now;i>=1;i--)
	{
		int p=(y>>i-1)&1;
		int temx=get(x,i);
		if(p==1)
		{
			if(h[temx]==1) return -1;
			tem=min(tem,temx);h[temx]=1;
		}
	}
	for(int i=1;i<=6;i++) if(h[i]) x=change_A(x,i,tem);
	x=(x<<3)+tem;
	x=small(x);
	return x;
}
void dfs(int x,int cnt,int be)
{
	if(cnt==K)
	{
		Q[++tot]=x;
		return;
	}
	for(int i=1;i<=be;i++) dfs((x<<3)+i,cnt+1,be);
	dfs((x<<3)+be+1,cnt+1,be+1);
}
void search(int x,int y)
{
	if(y==K)
	{
		int tem=find_Q(x);
		T.s[tem][1]++;
		return;
	}
	for(int i=0;i<(1<<y);i++)
	{
		int tem=make(x,i,y);
		if(tem==-1) continue;
		else search(tem,y+1);
	}
}
void prepare()
{
	int tem;
	for(int i=0;i<(1<<K);i++)
	{
		for(int j=1;j<=tot;j++)
		{
			int temx=Q[j];
			if(get_sum(temx,1)==1&&((i>>(K-1))&1)==0) continue;
			tem=make(temx,i,K);
			if(tem==-1) continue;
			int k=find_Q(tem);
			A.s[k][j]++;
		}
	}
}
void init()
{
	scanf("%d%lld",&K,&N);
	dfs(0,0,0);//将所有的状态最小表示
	sort(Q+1,Q+tot+1);
	T.make(0);T.n=tot;T.m=1;
	search(0,0);//第K个矩阵
	A.make(tot);
	prepare();//生成状态转移矩阵
	//A.print();
}
void work()
{
	miku ans=A;
	ans=quickpow(ans,N-K);
	//T.print();
	ans=ans*T;
	printf("%d",ans.s[1][1]);
}
int main()
{
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	init();
	work();
	return 0;
}