题目

这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！

题解

基本思想就是放置其实与棋局所放置的形状无关，直接对每一行进行讨论就行了（我开始以为是八皇后问题的变种，但由于没有斜行的约束条件，使得规划起来比八皇后问题简单很多，不用考虑之前行的棋盘形状） 用dp[i][j][k]存储第i行，j列一个棋子，k列两个棋子的方案数，每一行一共有6种放置方法（经过总结和合并后）

1. dp[i-1][j][k] （i行不放棋子） 2. dp[i-1][j-1][k]*(m-k-j+1) （放一个棋子在空列处） 3. dp[i-1][j-2][k]*((m-k-j+2)*(m-k-j+1)/2)（放两个棋子在空列处） 4. dp[i-1][j+1][k-1]*(j+1) （放一个棋子在单棋子列） 5. dp[i-1][j+2][k-2]*((j+2)*(j+1)/2) （放两个棋子在单棋子列） 6. dp[i-1][j][k-1]*j*(m-j-k+1) （放一个棋子在单棋子列，一个棋子在空列处） #include<bits/stdc++.h> #define ll long long #define int1 int using namespace std; int n,m; const int M=9999973; int x1=2,x2=0; ll dp[105][105][105]; void donggui(int i,int j,int k) { ll a1=dp[i-1][j][k]; ll a2=((j>=1)?dp[i-1][j-1][k]:0)*(m-k-j+1); ll a3=((j>=2)?dp[i-1][j-2][k]:0)*((m-k-j+2)*(m-k-j+1)/2); ll a4=((k>=1)?dp[i-1][j+1][k-1]:0)*(j+1); ll a5=((k>=2)?dp[i-1][j+2][k-2]:0)*((j+2)*(j+1)/2); ll a6=((k>=1)?dp[i-1][j][k-1]:0)*j*(m-j-k+1); dp[i][j][k]=((a1+a2+a3)%M+a4+a5+a6)%M; cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<endl; } void initial() { dp[1][2][0]=m*(m-1)/2; dp[1][1][0]=m; dp[1][0][0]=1; } int main() { cin>>n>>m; initial(); for(int i=2;i<=n;i++) { for(int j=0;j<=min(x1+2,m);j++)//columns with only one { for(int k=0;k<=min(x2+2,m);k++)//columns with two { if(j+k<=m) donggui(i,j,k); } } x2+=2; x1+=2; } ll ans1=0; for(int i=0;i<=m;i++) { for(int j=0;j<=m;j++) { if(i+j<=m) { ans1=(ans1+dp[n][i][j])%M; } } } cout<<ans1<<endl; }