记录编号 23380 评测结果 AAAAAAAAAA
题目名称 [AHOI2009] 中国象棋 最终得分 100
用户昵称 GravatarPom 是否通过 通过
代码语言 C++ 运行时间 0.455 s
提交时间 2011-03-09 17:23:57 内存使用 8.60 MiB
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN=103;
const int M=9999973;

long long f[MAXN][MAXN][MAXN],i,j,k,n,m,ans;

int main()
{
	freopen("cchess.in","r",stdin);
	freopen("cchess.out","w",stdout);
	scanf("%d%d",&n,&m);
	f[0][0][0]=1;
	for (i=1;i<=n;i++)
	{
		for (j=0;j<=m;j++)
			for (k=0;k<=m-j;k++)
			{
				int kong=m-j-k;
				f[i][j][k]=f[i-1][j][k];
				if (j)
				{
					f[i][j][k]+=f[i-1][j-1][k+1]*(k+1);
					if (j>1) f[i][j][k]+=f[i-1][j-2][k+2]*(k+2)*(k+1)/2;
				}
				if (k && j) f[i][j][k]+=f[i-1][j-1][k]*k*(kong+1);
				if (k>=2) f[i][j][k]+=f[i-1][j][k-2]*(kong+2)*(kong+1)/2;
				if (k) f[i][j][k]+=f[i-1][j][k-1]*(kong+1);
				f[i][j][k]=f[i][j][k]%M;
			}
	}
	for (i=0;i<=m;i++)
		for (j=0;j<=m;j++)
			ans+=f[n][i][j];
	ans=ans%M;
	cout<<ans<<endl;
	return 0;
}