 /**//*
題意: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;
}
|