「Bzoj 1801」「Ahoi2009」中国象棋 (组合数DP)

BZOJ 1801
题意：在一个$N$行$M$列的棋盘上，让你放若干个炮（可以是$0$个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好有一个棋子。

先是可以发现每行每列最多放两个棋子。
然后我们可以暴力剪枝过掉30分。
根据暴力思路，我们按行DP，列记录状态。
考虑优化，我们可以做一个三进制状压DP，记录每行的状态(放了0个，放了1个，放了2个)来DP。
实质上，我们不需要知道具体的棋盘是怎么样的，我们可以像Bzoj 1079那样记录。
设$dp(i,j,k)$为前$i$行有$j$列现在有$1$个棋子的，有$k$列现在有$2$个棋子的方案数。
这样就非常好转移了，具体看代码转移注释。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MO = 9999973, MAXN = 100 + 5;

    LL n, m, dp[MAXN][MAXN][MAXN];

    LL C(LL n) {return n * (n - 1ll) / 2ll % MO;}

    void clean() {
        ms(dp, 0);
    }
    int solve() {

        clean();
        cin >> n >> m;

        dp[0][0][0] = 1;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k + j <= m; ++k) {

                    // 1、不放 
                    dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MO;

                    // 2、放一个
                        // a 放在 0 列
                    if (m - j - k >= 0) dp[i + 1][j + 1][k] = (dp[i + 1][j + 1][k] + dp[i][j][k] * (m - j - k) % MO) % MO;
                        // b 放在 1 列
                    dp[i + 1][j - 1][k + 1] = (dp[i + 1][j - 1][k + 1] + dp[i][j][k] * j % MO) % MO; 

                    // 3、放两个
                        // a 放在 0 0
                    if (m - j - k >= 0) dp[i + 1][j + 2][k] = (dp[i + 1][j + 2][k] + dp[i][j][k] * C(m - j - k) % MO) % MO; 
                        // b 放在 1 1
                    dp[i + 1][j - 2][k + 2] = (dp[i + 1][j - 2][k + 2] + dp[i][j][k] * C(j) % MO) % MO; 
                        // c 放在 0 1
                    if (m - j - k >= 0) dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k] * j % MO * (m - j - k) % MO) % MO;

                }
            }
        }

        LL ans = 0;

        for (int j = 0; j <= m; ++j) {
            for (int k = 0; k + j <= m; ++k) {
                ans = (ans + dp[n][j][k]) % MO;
            }
        }

        cout << ans;

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}