比赛 AHOI09DAY2模拟 评测结果 AAAAAAAAAA
题目名称 中国象棋 最终得分 100
用户昵称 .Xmz 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-03-09 11:18:59
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;

const int mod=9999973;

int f[101][101][101];
int n,m;
int ans;

void dp()
{
	f[0][0][0]=1;
	for (int t=0;t<n;t++)
	{
		for (int i=min(t,m);i>=0;i--)
		for (int j=min(t*2,m-i);j>=0;j--)
		{
			int k=m-i-j;
			f[t+1][i][j]+=f[t][i][j];
			if (j>0) f[t+1][i+1][j-1]+=(f[t][i][j]*j)%mod;
			if (k>0) f[t+1][i][j+1]+=(f[t][i][j]*k)%mod;
			if (j>0 && k>0) f[t+1][i+1][j]+=(((f[t][i][j]*j)%mod)*k)%mod;
			if (j>1)
			{
				if (j & 1) f[t+1][i+2][j-2]+=(((f[t][i][j]*j)%mod)*((j-1)/2))%mod;
				else f[t+1][i+2][j-2]+=(((f[t][i][j]*(j/2))%mod)*(j-1))%mod;
			}
			if (k>1) 
			{
				if (k & 1) f[t+1][i][j+2]+=(((f[t][i][j]*k)%mod)*((k-1)/2))%mod;
				else f[t+1][i][j+2]+=(((f[t][i][j]*(k/2))%mod)*(k-1))%mod;
			}
			if (j>0) f[t+1][i+1][j-1]%=mod;
			f[t+1][i][j+1]%=mod;
			if (j>1) f[t+1][i+2][j-2]%=mod;
			f[t+1][i][j+2]%=mod;
			f[t+1][i+1][j]%=mod;
			f[t+1][i][j]%=mod;
		}
	}
	for (int i=m;i>=0;i--)
	for (int j=m;j>=0;j--)
	ans=(ans+f[n][i][j])%mod;
}
int main()
{
	freopen("cchess.in","r",stdin);
	freopen("cchess.out","w",stdout);
	scanf("%d%d",&n,&m);
	if (n<m) swap(n,m);
	dp();
	printf("%d\n",ans);
	return 0;
}