链接：点击打开链接
题意：n*m的棋盘，有多少种放象棋中炮的方式，使得两两之间不能互相伤害
代码：
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; const long long MOD=9999973; const long long ex_MOD=19999947; long long dp[105][105][105]; int main(){ long long n,m,i,j,k,ans; while(scanf("%lld%lld",&n,&m)!=EOF){ memset(dp,0,sizeof(dp)); dp[0][0][0]=1; //dp[i][j][k]表示i行，j列放一个，k列放两个 for(i=1;i<=n;i++){ for(j=0;j<=m;j++){ for(k=0;k+j<=m;k++){ //不放 dp[i][j][k]=dp[i-1][j][k]; if(j>=1){ //放一个，用来增加j dp[i][j][k]+=dp[i-1][j-1][k]*(m-(j-1)-k); dp[i][j][k]%=MOD; } if(k>=1){ //取一个用来增加k dp[i][j][k]+=dp[i-1][j+1][k-1]*(j+1); dp[i][j][k]%=MOD; } if(j>=2){ //放两个增加j dp[i][j][k]+=dp[i-1][j-2][k]*(m-(j-2)-k)*(m-(j-2)-k-1)>>1; dp[i][j][k]%=MOD; } if(k>=1){ //挪一个放一个 dp[i][j][k]+=dp[i-1][j][k-1]*j*(m-(k-1)-j); dp[i][j][k]%=MOD; } if(k>=2){ //将两个j变成两个k dp[i][j][k]+=dp[i-1][j+2][k-2]*(j+2)*(j+1)>>1; dp[i][j][k]%=MOD; } } } } ans=0; for(i=0;i<=m;i++) for(j=0;i+j<=m;j++) ans=(ans+dp[n][i][j])%MOD; printf("%lld\n",ans); } return 0; }