1801: [Ahoi2009]chess 中国象棋
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1426 Solved: 826
[Submit][Status][Discuss]
Description
在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法，中国像棋中炮的行走方式大家应该很清楚吧.
Input
一行包含两个整数N，M，中间用空格分开.
Output
输出所有的方案数，由于值比较大，输出其mod 9999973
Sample Input
1 3
Sample Output
7
HINT
除了在3个格子中都放满炮的的情况外，其它的都可以.
100%的数据中N,M不超过100
50%的数据中，N,M至少有一个数不超过8
30%的数据中，N,M均不超过6
----------------------------------------------------------
将题目化简为设计01矩阵 每一行每一列至多2个1。求有几种方案。
设f[i][j][k]代表到第i行有j列放了1个象棋k列放了0个象棋有两个象棋的列不用考虑因为不能再放了。
递推方程如下：
f[i][j][k]=f[i-1][j][k] 第i行不放。
f[i][j][k]+=f[i-1][j-1][k+1]*(k+1) 在i-1行中任选一列（该列的棋子数=0）后面放一颗。有 k+1种放法。
f[i][j][k]+=f[i-1][j+1][k]*(j+1) 选一列（该列棋子数=1）
f[i][j][k]+=f[i-1][j][k+1]*j*(k+1) 选两列 一列棋子数=1 一列棋子数=0
f[i][j][k]+=f[i-1][j-2][k+2]*(k+2)*(k+1)/2 选两列棋子数=0的
f[i][j][k]+=f[i-1][j+2][k]*(j+2)*(j+1)/2 选两列棋子数=1的
最后统计 f[n][i][j] 0<=i,j<=m;
代码如下：
#include<cstdio>
#include<iostream>
#define MOD 9999973
#define MAXN 105
#define For(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
long long f[MAXN][MAXN][MAXN];
int main()
{
int n,m;cin>>n>>m;
f[][][m]=;
f[][][m-]=m;
f[][][m-]=m*(m-)/;
For(i,,n)
{
For(j,,m)
{
For(k,,m)
{
f[i][j][k]=(f[i-][j][k]+f[i-][j-][k+]*(k+)%MOD+f[i-][j+][k]*(j+)%MOD)%MOD+f[i-][j][k+]*j*(k+)%MOD;
f[i][j][k]+=(f[i-][j-][k+]*(k+)*(k+)/)%MOD+f[i-][j+][k]*(j+)*(j+)/;
f[i][j][k]%=MOD;
}
}
}
long long ans=;
For(i,,m)
{
For(j,,m)
{
ans+=f[n][i][j];
ans%=MOD;
}
}
printf("%lld",ans);
}