[Leaf] [P2051] 中国象棋

luogu-p2051-中国象棋">Luogu-P2051 中国象棋

1. 题面梗概

中译中: $N \times M$ 的棋盘，放炮。要求每行、每列最多只能放 2 个炮。求总共有多少种放法。

2. 逻辑推导

题目很简洁，每列限制放两个炮，看起来像状压？但 $M = 100$，复杂度会爆炸到外太空。

显然是个动态规划的题，我们考虑拆解状态。

因为我们是一行一行放炮，所以对于下一行炮的放置，它真的需要关心上一行炮的位置吗？

答案是不关心，它只关心：有几列没有炮，有几列只放了 1 个炮，有几列放了 2 个炮。

我们发现，具体列的信息没有意义，每一列的状态统计更为重要。

2.1 DP

既然如此，我们考虑这样定义 DP：$f[i][j][k]$ 表示：前 $i$ 行，有 $j$ 列放了 $1$ 个炮，$k$ 列放了 $2$ 个炮，自然 $M - j - k$ 列放了 $0$ 个炮。

接着我们考虑怎么转移状态：这一行我们有三种选择，不放，放 1 个，放 2 个炮，然后具体放在那一列呢？

• 放 1 个在 0 炮列：$j \to j+1$。

• 放 1 个在 1 炮列：$j \to j-1, k \to k+1$。

• 放 2 个在 0 炮列：$j \to j+2$。

• 放 2 个在 1 炮列：$j \to j-2, k \to k+2$。

• 一个 0 炮列，一个 1 炮列：$k \to k+1$。

至于系数的处理，我们利用组合数 $C(x,1)$ 和 $C(x,2)$ 即可快速算出。

3. 代码实现

▶

AcCode

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

const int maxn = 105;
const int mod = 9999973;

long long dp[maxn][maxn][maxn];
int n, m;

void calc( int i, int j, int k, long long add ) {
    dp[i][j][k] = ( dp[i][j][k] + add ) % mod;
}

long long c2( int x ) {
    return x * (x - 1) / 2;
}

int main()
{	
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    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 )
            {
                if( !dp[i][j][k] ) continue;
                long long cur = dp[i][j][k];
                int z = m - j - k;
                
                calc( i+1, j, k, cur );

                if( z >= 1 ) {
                    calc( i+1, j+1, k, cur * z );
                }
                if( j >= 1 ) {
                    calc( i+1, j-1, k+1, cur * j );
                }
                if( z >= 2 ) {
                    calc( i+1, j+2, k, cur * c2( z ) );
                }
                if( j >= 2 ) {
                    calc( i+1, j-2, k+2, cur * c2( j ) );
                }
                if( j >= 1 && z >= 1 ) {
                    calc( i+1, j, k+1, cur * z * j );
                }
            }
        }
    }

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

    cout << ans << '\n';
    return 0;
}

4. 复盘

• 复杂度: $O( NM^2 )$。

• 碎碎念: 这题关键在于 DP 状态设计中的特征提取——当具体位置不影响后续决策时，直接统计特征数量可以降维指数级的复杂度。

• 关联笔记: [[计数DP]]