LGOJP2051 [AHOI2009]中国象棋

比较明显的计数dp。不知道为什么被打了状压的tag...
不难发现无论炮放在哪里其实是等价的，需要知道的只有这一列放了一个炮还是两个炮还是还没放，那么可以设\(f[i,j,k]\)表示第\(i\)行，一共有\(j\)列放了两个炮，\(k\)列放了一个炮。
然后转移考虑一下选数的组合意义即可。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 100010;
const int mod = 9999973;

int n, m, fac[N], inv[N];
int f[110][110][110];
// f[i][j][k] 表示前i行，然后有j列放了两个，k列放了一个

int power(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod; b >>= 1;
    }
    return ans;
}

int C(int n, int m) {
    if(n > m) return 0;
    return 1ll * fac[m] * inv[m - n] % mod * inv[n] % mod;
}

int main() {
    scanf("%d%d", &n, &m);
    fac[0] = inv[0] = 1;
    for(int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    for(int i = 1; i < N; ++i) inv[i] = power(fac[i], mod - 2);
    f[0][0][0] = 1;
    for(int i = 0; i < n; ++i) 
        for(int j = 0; j <= m; ++j) 
            for(int k = 0; j + k <= m; ++k) 
                if(f[i][j][k]) {
                    // 不放
                    (f[i + 1][j][k] += f[i][j][k]) %= mod;
                    // 放一个
                    if(k + 1 <= m) (f[i + 1][j][k + 1] += 1ll * f[i][j][k] * C(1, m - j - k) % mod) %= mod;
                    if(j + 1 <= m && k) (f[i + 1][j + 1][k - 1] += 1ll * f[i][j][k] * C(1, k) % mod) %= mod;
                    // 放两个
                    if(j + 2 <= m && k >= 2) (f[i + 1][j + 2][k - 2] += 1ll * f[i][j][k] * C(2, k) % mod) %= mod;
                    if(k + 2 <= m) (f[i + 1][j][k + 2] += 1ll * f[i][j][k] * C(2, m - j - k) % mod) %= mod;
                    if(j + 1 <= m) (f[i + 1][j + 1][k] += 1ll * f[i][j][k] * C(1, m - j - k) % mod * C(1, k) % mod)  %= mod;
                }
    int ans = 0;
    for(int i = 0; i <= m; ++i) {
        for(int j = 0; i + j <= m; ++j) {
            (ans += f[n][i][j]) %= mod;
//          printf("%d %d %d\n", i, j, f[n][i][j]);
        }
    }
//  puts("");
    printf("%d\n", ans);
}

LGOJP2051 [AHOI2009]中国象棋

原文：https://www.cnblogs.com/henry-1202/p/11741805.html