Description
在 $n * m$ 的格子上放若干个炮， 使得每个炮都不能攻击到其他炮
Solution
定义数组f[ i ][ j ][ k ] 表示到了第 i 行， 已经有2个炮的列数为 j， 有1个炮的列数 为k， 的方案数有多少。
然后就能非常简单的写个dp了
Code
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define ll long long 5 #define rep(i,a,b) for(int i = (a); i <= (b); ++i) 6 #define per(i,a,b) for(int i = (a); i >= (b); --i) 7 #define rd read() 8 using namespace std; 9 10 const int N = 105; 11 const int mod = 9999973; 12 13 int n, m, op, ans; 14 int f[2][N][N]; 15 16 int read() { 17 int X = 0, p = 1; char c = getchar(); 18 for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1; 19 for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0'; 20 return X * p; 21 } 22 23 int C(int a) { 24 return ((a - 1) * a / 2) % mod; 25 } 26 27 int main() 28 { 29 n = rd; m = rd; 30 f[0][0][0] = 1; 31 rep(i, 1, n) { 32 op ^= 1; 33 rep(j, 0, m) rep(k, 0, m - j) { 34 f[op][j][k] = f[op ^ 1][j][k]; 35 if(k >= 1) f[op][j][k] = (f[op][j][k] + 1LL * (m - j - k + 1) * f[op ^ 1][j][k - 1] % mod) % mod; 36 if(j >= 1) f[op][j][k] = (f[op][j][k] + 1LL * (k + 1) * f[op ^ 1][j - 1][k + 1] % mod) % mod; 37 if(k >= 2) f[op][j][k] = (f[op][j][k] + 1LL * C(m - j - k + 2) * f[op ^ 1][j][k - 2] % mod) % mod; 38 if(j >= 1) f[op][j][k] = (f[op][j][k] + 1LL * k * (m - j + 1- k) % mod * f[op ^ 1][j - 1][k] % mod) % mod; 39 if(j >= 2) f[op][j][k] = (f[op][j][k] + 1LL * C(k + 2) * f[op ^ 1][j - 2][k + 2] % mod) % mod; 40 } 41 } 42 rep(i, 0, m) rep(j, 0, m - i) ans = (ans + f[op][i][j]) % mod; 43 ans = (ans % mod + mod) % mod; 44 printf("%d ", ans); 45 }