比赛 AHOI09DAY2模拟 评测结果 RRRRRRRRRR
题目名称 跳棋 最终得分 0
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-03-09 12:08:52
显示代码纯文本
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=105;
const int MO=9999973;

typedef unsigned long long u64;

int N,M;
int used[MAXN];
//int show[MAXN][MAXN];
int s[MAXN][2],tot[MAXN];
u64 re;

inline u64 getfac(int s,int t,int same)
{
	u64 ans=1;
	for(int i=s;i<=t;i++)
	{
		int j=i;
		while(same && ((j&1)==0))same--,j/=2;
		ans=ans*j%MO;
	}
	return ans;
}

void dfs(int dep,int now1,int now2,int same,int before)
{
	re+=getfac(N-dep+1,N,same);
	re%=MO;
	if (dep==N)
		return ;
	for(int i=now1;i<M;i++)
		if (used[i]<2)
		{
			//show[dep][i]=1;
			used[i]++;
			if (i!=now1) dfs(dep+1,i,i+1,same,1);
			else if (before<=1) dfs(dep+1,i,i+1,same+1,1);
			if (i==now1 && now2<M && used[now2]<2)
			{
				used[now2]++;
				//show[dep][now2]=1;
				if (before==2) dfs(dep+1,now1,now2,same+1,2);
				else dfs(dep+1,now1,now2,same,2);
				used[now2]--;
				//show[dep][now2]=0;
			}		
			int j=(i==now1)?(now2+1):(i+1);
			for(;j<M;j++)
				if (used[j]<2)
				{
					//show[dep][j]=1;
					used[j]++;
					dfs(dep+1,i,j,same,2);
					//show[dep][j]=0;
					used[j]--;
				}
			used[i]--;
			//show[dep][i]=0;
		}
}

int main()
{
	freopen("cchess.in","r",stdin);
	freopen("cchess.out","w",stdout);
	scanf("%d%d",&N,&M);
	if (N<M)
		swap(N,M);
	dfs(0,0,1,0,0);
	printf("%lld\n",re);
	return 0;
}