比赛 HAOI2009 模拟试题3 评测结果 ATTTTTTATT
题目名称 诸侯安置 最终得分 20
用户昵称 zqzas 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2009-04-23 11:20:46
显示代码纯文本
#include <iostream>

#define MAXN 210

const int P=504;
int ans,ori_n,n,k,map[MAXN][MAXN];
bool used[MAXN],data[MAXN][MAXN];

void dfs(int x,int now)
{
	if (now>=k)
	{
		ans++;
		ans%=P;
		return;
	}
	if (x>n)
		return;
	//do not use this one
	dfs(x+1,now);
	//use this one
	int i,y;
	for (i=1;i<=map[x][0];i++)
	{
		y=map[x][i];
		if (!used[y])
		{
			used[y]=true;
			dfs(x+1,now+1);
			used[y]=false;
		}
	}
}

void run()
{
	dfs(1,0);
}

void make()
{
	int i,j,d;
	for (i=ori_n;i<=n;i++)
	{
		d=i-ori_n;
		for (j=1+d;j<=n-d;j++)
		{
			data[i][j]=true;
			data[n+1-i][j]=true;
		}
	}
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			if (data[i][j])
				map[i][++map[i][0]]=j;
}

void ini()
{
	scanf("%d%d",&ori_n,&k);
	n=ori_n*2-1;
	make();
}

int main()
{
	freopen("empire.in","r",stdin);
	freopen("empire.out","w",stdout);
	ini();
	run();
	printf("%d",ans%P);
	return 0;
}