Luogu 2051[AHOI2009]中国象棋 - DP

Description

在 $n * m$ 的格子上放若干个炮， 使得每个炮都不能攻击到其他炮

Solution

定义数组f[ i ][ j ][ k ] 表示到了第 i 行， 已经有2个炮的列数为 j， 有1个炮的列数 为k， 的方案数有多少。

然后就能非常简单的写个dp了

Code

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define ll long long

 #define rep(i,a,b) for(int i = (a); i <= (b); ++i)

 #define per(i,a,b) for(int i = (a); i >= (b); --i)

 #define rd read()

 using namespace std;

 const int N = ;

 const int mod = ;

 int n, m, op, ans;

 int f[][N][N];

 int read() {

     int X = , p = ; char c = getchar();

     for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;

     for(; c >= '' && c <= ''; c = getchar()) X = X *  + c - '';

     return X * p;

 }

 int C(int a) {

     return ((a - ) * a / ) % mod;

 }

 int main()

 {

     n = rd; m = rd;

     f[][][] = ;

     rep(i, , n) {

         op ^= ;

         rep(j, , m) rep(k, , m - j) {

             f[op][j][k] = f[op ^ ][j][k];

             if(k >= ) f[op][j][k] = (f[op][j][k] + 1LL * (m - j - k + ) * f[op ^ ][j][k - ] % mod) % mod;

             if(j >= ) f[op][j][k] = (f[op][j][k] + 1LL * (k + ) * f[op ^ ][j - ][k + ] % mod) % mod;

             if(k >= ) f[op][j][k] = (f[op][j][k] + 1LL * C(m - j - k + ) * f[op ^ ][j][k - ] % mod) % mod;

             if(j >= ) f[op][j][k] = (f[op][j][k] + 1LL * k * (m - j + - k) % mod * f[op ^ ][j - ][k] % mod) % mod;

             if(j >= ) f[op][j][k] = (f[op][j][k] + 1LL * C(k + ) * f[op ^ ][j - ][k + ] % mod) % mod;

         }

     }

     rep(i, , m) rep(j, , m - i) ans = (ans + f[op][i][j]) % mod;

     ans = (ans % mod + mod) % mod;

     printf("%d\n", ans);

 }