比赛 |
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;
}