象棋，给你棋盘大小，然后放炮（炮的数量不限），不能让炮打到其他的炮，问方案数；
数据n,m<=200;
状态压缩似乎能做，但是我不会；
因为只要状态数，所以不必纠结每种状态的具体情况；
可以想出每行每列最多放两个棋子（我想到了吗？）；
所以（为什么啊） 设计f[i][j][k]
表示DP到第i行，一列只有一个棋子的有j个，一列只有两个棋子的有k个；
清晰（模糊）转移方法
好，我们终于来到了第i行，加油；
这位OIer并不打算把棋子放在这一行，用f[i][j][k]直接继承f[i-1][j][k]的方案数；
然而(zhu)队友并不想就这样进入下一行，他要放棋子了！
请大家睁大眼睛，他在纠结
因为他最多只能放两个棋子，每一个棋子的位置都影响着当前的方案数；
他现在想放一个棋子，
两种选择：一，放在一列没有棋子的位置上，这样f[i][j][k]+=f[i][j-1][k]*(m-j+1-k)(乘法法则，有j-1个位置可以选)
二，放在一列只有一个棋子的位置上，这样f[i][j][k]+=f[i-1][j+1][k-1]*(j+1);
放两个棋子
（这个zhu队友想到现在头都大了，但是他离胜利不远了）
一，两个都放在没有棋子的一列，f[i][j][k]+=f[i-1][j-2][k]*(C(m-j-k+2)) (组合数，剩下的列中选两个位置，下面有代码)、
二，两个都放在有一个棋子的列上，f[i][j][k]+=f[i-1][j+2][k-2]*((j+2)*(j+1)/2) (组合数公式) （要时常记得，j+k<=m,如果放在j上，k会增加，j会减小）
三，一个放在没有棋子的列上，一个放在有一个棋子的列上，f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1) (j个位置有一个，但是一个放在这列j-1，另一个令j+1)
（队友阵亡，因为他没有判断边界）；
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int mo=9999973; const int maxn=120; ll f[maxn][maxn][maxn]; int n,m; ll C(ll x) { return (x*(x-1)/2); } ll ans; int main() { scanf("%d%d",&n,&m); f[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++) { f[i][j][k]=f[i-1][j][k]; if(k>=1) f[i][j][k]+=f[i-1][j+1][k-1]*(j+1); if(j>=1) f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1); if(k>=2) f[i][j][k]+=f[i-1][j+2][k-2]*((j+2)*(j+1)/2); if(k>=1) f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1); if(j>=2) f[i][j][k]+=f[i-1][j-2][k]*C(m-j-k+2); f[i][j][k]%=mo; } } } for(int i=0;i<=m;i++) { for(int j=0;j<=m-i;j++) { ans+=f[n][i][j]; ans%=mo; } } printf("%lld",ans); return 0; }