 /**//*
题意:n*m的棋盘,要放中国象棋的炮,问有多少种合法的放法(空也算一种)
对于炮,只要没有3个或以上的在同一行或同一列就算合法了
sample:
1*3 的棋盘有7种
不放 算1种
放1个炮的有3种
放2个炮的有3种

可以知道每一行、一列最多只能放2个炮。即可以放0,1,2个
通过记录之前那些放0个炮,1个炮,2个炮的列的数目即可!!
dp[n,x,y]表示在前n行中,放0个炮的列数为x,放1个炮的列数为y 的方案数
转移即在该行 不放,放1个,放2个
不放
dp[n,x,y] ->dp[n+1,x,y]

放1个,可放在x,也可放在y
dp[n,x,y] *x ->dp[n+1,x-1,y+1]
dp[n,x,y] *y ->dp[n+1,x,y-1]

放2个,2个都放在x,2个都放在x,1个x 1个y
dp[n,x,y] *c(x,2) ->dp[n+1,x-2,y+2]
dp[n,x,y] *c(y,2) ->dp[n+1,x,y-2]
dp[n,x,y] *x*y ->dp[n+1,x-1,y]

从当前状态推到后继状态会容易理解一点

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1801
*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 105;
const int mod = 9999973;

int dp[2][maxn][maxn];//前i行 炮个数为0的列数 炮个数为1的列数

int main()
  {

int n,m;
while(~scanf("%d%d",&n,&m))
 {
if(n<m)swap(n,m);
int now = 1,next = 0;
memset(dp[next],0,sizeof(dp[next]));
dp[next][m][0]=1;//
for(int i=0;i<n;i++)
 {
swap(now,next);
memset(dp[next],0,sizeof(dp[next]));
for(int a0=0;a0<=m;a0++)
for(int a1=0;a0+a1<=m;a1++)
if(dp[now][a0][a1])
 {
int t=dp[now][a0][a1];

//not put
dp[next][a0][a1]+=t;
dp[next][a0][a1]%=mod;

//put one
if(a0)
 {
dp[next][a0-1][a1+1]+=(long long)t*a0%mod;
dp[next][a0-1][a1+1]%=mod;
}
if(a1)
 {
dp[next][a0][a1-1]+=(long long)t*a1%mod;
dp[next][a0][a1-1]%=mod;
}
//put two
if(a0>=2)
 {
dp[next][a0-2][a1+2]+=(long long)t*a0*(a0-1)/2%mod;
dp[next][a0-2][a1+2]%=mod;
}
if(a1>=2)
 {
dp[next][a0][a1-2]+=(long long)t*a1*(a1-1)/2%mod;
dp[next][a0][a1-2]%=mod;
}
if(a0&&a1)
 {
dp[next][a0-1][a1]+=(long long)t*a0*a1%mod;
dp[next][a0-1][a1]%=mod;
}
}
}

long long ans = 0;
for(int a0=0;a0<=m;a0++)
for(int a1=0;a0+a1<=m;a1++)
 {
ans+=dp[next][a0][a1];
}
printf("%lld\n",ans%mod);
}
return 0;
}
|