[文章目录]
Description
在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法，中国像棋中炮的行走方式大家应该很清楚吧.
显然DP，不过由于想到状压的原因，不能表示状态。所以不用表示状态啊，只需要表示有一个炮的列的个数，有两个炮的列数。然后转移就好了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n,m,ans;
ll dp[110][110][110];
const ll mod=9999973;
int main()
{
scanf("%lld%lld",&n,&m);
dp[0][0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=(m-j);k++)
{
dp[i][j][k]=dp[i-1][j][k];
if(k-1>=0&&j+1<=m)dp[i][j][k]+=(dp[i-1][j+1][k-1]*(j+1)%mod);
if(k-2>=0&&j+2<=m)dp[i][j][k]+=(dp[i-1][j+2][k-2]*(j+2)*(j+1)/2%mod);
if(j-1>=0)dp[i][j][k]+=(dp[i-1][j-1][k]*(m-j-k+1)%mod);
if(j-2>=0)dp[i][j][k]+=(dp[i-1][j-2][k]*(m-j-k+2)*(m-j-k+1)/2%mod);
if(j>=1&&k-1>=0&&m-j-k+1>=1) dp[i][j][k]+=(dp[i-1][j][k-1]*j*(m-j-k+1)%mod);
dp[i][j][k]%=mod;
}
for(int j=0;j<=m;j++)
for(int k=0;k<=(m-j);k++)
ans=(ans+dp[n][j][k])%mod;
printf("%lld",ans);
return 0;
}