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