在n*m的棋盘中放炮，使得他们不能相互攻击的方案数。
也就是说同一行/列不能有超过两个炮。 似曾相识的感觉（其实是我SB没想到更简单的状态表示） 于是我把他当成二分图，同一个点至多匹配两次，dp统计方案数。 f[i][j][k] 表示左边用了i个点，右边j个点匹配了两次，k个点匹配了一次。 后来发现其实等价于前i行，j个列有两个炮，k个列一个炮。 瞎转移就好了，情况略多，头脑要清晰。 code:
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #define LL long long using namespace std; const LL mod=9999973; LL n,m,c[150][3],f[110][110][110]; void pre() { memset(c,0,sizeof(c)); c[0][0]=1; for(LL i=1;i<=110;i++) { c[i][0]=1; for(LL j=1;j<=2&&j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; } } int main() { pre(); scanf("%lld %lld",&n,&m); memset(f,0,sizeof(f)); f[0][0][0]=1; for(LL i=1;i<=n;i++) for(LL j=0;j<=m;j++) for(LL k=0;k<=m-j;k++) { if(2*i<j*2+k) break; if(j>=1) (f[i][j][k]+=f[i-1][j-1][k+1]*(k+1))%=mod; (f[i][j][k]+=f[i-1][j][k-1]*(m-k+1-j))%=mod; if(k>=2) (f[i][j][k]+=f[i-1][j][k-2]*c[m-k+2-j][2])%=mod; if(j>=1) (f[i][j][k]+=f[i-1][j-1][k]*k%mod*(m-j+1-k))%=mod; if(j>=2) (f[i][j][k]+=f[i-1][j-2][k+2]*c[k+2][2])%=mod; (f[i][j][k]+=f[i-1][j][k])%=mod; } LL ans=0; for(LL j=0;j<=m;j++) for(LL k=0;k<=m-j;k++) (ans+=f[n][j][k])%=mod; printf("%lld",ans); }