除了在3个格子中都放满炮的的情况外，其它的都可以.
100%的数据中N,M不超过100
50%的数据中，N,M至少有一个数不超过8
30%的数据中，N,M均不超过6
#include <bits/stdc++.h> using namespace std; const int mod = 9999973; typedef long long ll; int n,m; ll f[105][105][105]; int C(int m){ return m*(m-1)/2; } 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){ //don‘t push f[i][j][k] = f[i-1][j][k]; //push 1 in the cow had 0 if (j > 0) f[i][j][k] = (f[i][j][k] + f[i-1][j-1][k]*(m-j-k+1)) % mod; //push 1 in the cow had 1 if (k > 0 && j+1 <= m) f[i][j][k] = (f[i][j][k] + f[i-1][j+1][k-1] * (j+1)) % mod; //push 2 in the cow had 0 if (j >= 2) f[i][j][k] = (f[i][j][k] + f[i-1][j-2][k] * C(m-j-k+2)) % mod; //push 1 in the cow had 0 && push 1 in the cow had 1 if (j && k) f[i][j][k] = (f[i][j][k] + f[i-1][j][k-1] * (m-j-k+1) * (j)) % mod; //push 2 in the cow had 1 if (k >= 2 && j+2 <= m) f[i][j][k] = (f[i][j][k] + f[i-1][j+2][k-2] * C(j+2)) % mod; } } } ll ans = 0; for (int j = 0;j <= m;++j){ for (int k = 0;k <= m-j;++k){ ans = (ans + f[n][j][k]) % mod; } } printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/mizersy/p/9736429.html