ZOJ 3822 Domination：棋盤覆蓋期望 DP

問題描述

N×M 棋盤（N,M ≤ 50）。每天在隨機空格放一個棋子。求期望天數，使得每行每列至少有一個棋子（即棋盤被「支配」）。

狀態定義

三維 DP：dp[i][j][k] = 放了 k 個棋子後，覆蓋了 i 行、j 列的概率。
目標：E = Σ_{k} k * dp[N][M][k]。

轉移方程推導

考慮第 k 個棋子放置時的四種情況（基於前 k-1 步狀態）：

1. 落在已覆蓋的行、列交叉區：i*j - (k-1) 格（已放 k-1 子，剩餘空格）。概率 p1。
2. 落在已覆蓋行、新列：i*(M-j) 格。概率 p2。
3. 落在新行、已覆蓋列：(N-i)*j 格。概率 p3。
4. 落在新行、新列：(N-i)*(M-j) 格。概率 p4。

總空格數：N*M - (k-1)。
轉移：

dp[i][j][k] = p1 * dp[i][j][k-1]
            + p2 * dp[i][j-1][k-1]
            + p3 * dp[i-1][j][k-1]
            + p4 * dp[i-1][j-1][k-1]

邊界條件

• dp[0][0][0] = 1。
• 若 i==N && j==M（已覆蓋全盤），後續放子不再改變行列覆蓋狀態，故 p1 項保留，但 p2,p3,p4=0。即：
  dp[N][M][k] = (N*M - k + 1) / (N*M - k + 1) * dp[N][M][k-1] = dp[N][M][k-1]。
  實際上一旦達到 (N,M) 就不再轉移出去，概率質量集中在 dp[N][M][*]。

期望計算

ans = Σ_{k=1..N*M} k * dp[N][M][k]。

核心代碼

double dp[55][55][2555];

int main() {
    int cas, n, m;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%d", &m, &n);  // 注意輸入順序：N 行 M 列
        int maxn = n * m;
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;

        for (int i=1; i<=m; i++)      // 列
            for (int j=1; j<=n; j++)  // 行
                for (int k=1; k<=maxn; k++) {
                    double base = maxn - k + 1;
                    dp[i][j][k] += (m-i+1)*(n-j+1) * dp[i-1][j-1][k-1];
                    dp[i][j][k] += j*(m-i+1) * dp[i-1][j][k-1];
                    dp[i][j][k] += i*(n-j+1) * dp[i][j-1][k-1];
                    if (i!=m || j!=n)
                        dp[i][j][k] += (i*j - k + 1) * dp[i][j][k-1];
                    dp[i][j][k] /= base;
                }

        double ans = 0;
        for (int i=1; i<=maxn; i++) ans += dp[m][n][i] * i;
        printf("%.10lf\n", ans);
    }
    return 0;
}

複雜度分析

• 狀態數：N × M × (N*M) ≤ 50×50×2500 = 6.25e6。
• 每狀態 O(1) 轉移，總操作 ~600 萬，極快。
• 空間：55×55×2555 × 8B ≈ 60 MB，略大但可接受（可優化滾動數組）。

關鍵細節

• 循環順序：i,j,k 遞增，依賴 k-1 層和更小 i,j，順序正確。
• i*j >= k 才有意義（否則概率 0），可加 if (i*j < k) continue; 剪枝。
• 輸入順序：題目給 N M，代碼讀為 m n 對應列 行，注意一致性。
• 期望公式 Σ k * P(恰在第 k 步完成) 等價於 Σ P(第 k 步未完成)，但直接累加 k * dp[N][M][k] 更直觀。