众所周知，双炮叠叠将是中国象棋中很厉害的一招必杀技。炮吃子时必须隔一个棋子跳吃，即俗称”炮打隔子”。 炮跟炮显然不能在一起打起来，于是rly一天借来了许多许多的炮在棋盘上摆了起来……他想知道，在N×M的矩形 方格中摆若干炮（可以不摆）使其互不吃到的情况下方案数有几种。 棋子都是相同的。 Input 一行，两个正整数N和M。 N<=100,M<=100 Output 一行，输出方案数mod 999983。 Sample Input 1 3 Sample Output 7
思路：每一行每一列的炮耳朵数量都不能超过两个。考虑用dp来做。 dp[i][j][k]，表示到第i层，前面放置了一个炮的列的数量为 j，放置了两个炮的数量为k，放置了0个炮的数量为m-j-k的状态总数。第i层状态由第i-1层状态转移来，在第i层我们可以放一个炮，两个炮，或者一个都不放。具体转移方程看代码
代码如下
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <queue> #include <cstdio> #include <map> using namespace std; #define LL long long int const int mod=999983; LL dp[105][105][105]; int sol(int x) { return x*(x-1)/2%mod; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { dp[0][0][0]=1; for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k+j<=m;k++) { dp[i][j][k]=dp[i-1][j][k];//一个炮都不放 if(j>=1) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k]*(m-j-k+1))%mod;//假设第i行摆放了一个炮，放在了没有炮的列上 if(j>=2) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-2][k]*sol(m-j-k+2))%mod;//假设第i行摆放了两个炮，放在了两个没有炮的列上 if(k>=1) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+1][k-1]*(j+1))%mod;//假设第i行放了一个，且放在了只有一个炮的列上 if(k>=1) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k-1]*(m-j-k+1)*j)%mod;//假设第i行放了两个，第一个放在了没有炮的列，第二个放在了只有一个炮的列上 if(k>=2) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+2][k-2]*sol(j+2))%mod;//假设第i行放了两个，放在了两个只有一个炮的列上 } int sum=0; for(int i=0;i<=m;i++) for(int j=0;j+i<=m;j++) sum=(sum+dp[n][i][j])%mod; printf("%d\n",sum); } return 0; }