ZOJ 3822 Domination：期望 DP 计算棋盘覆盖天数

题目大意

N×M 棋盘（≤50×50），每天在随机空格放一子。求期望天数，使得每行每列至少有一子（即被「支配」）。

DP 状态定义

dp[i][j][k]：已有 i 行、j 列被覆盖，共放了 k 个子的概率。
转移（放第 k+1 个子）：

• 落在已覆盖行列交叉：(i*j - k) / (N*M - k) → dp[i][j][k+1]
• 落在新行已覆盖列：( (N-i)*j ) / (N*M - k) → dp[i+1][j][k+1]
• 落在已覆盖行新列：( i*(M-j) ) / (N*M - k) → dp[i][j+1][k+1]
• 落在新行新列：( (N-i)*(M-j) ) / (N*M - k) → dp[i+1][j+1][k+1]

期望计算

E = Σ_{k} k * dp[N][M][k]

C++ 实现

#include 
#include 
#include 
using namespace std;

const int MAXK = 66*66;
double dp[55][55][MAXK];
int N, M;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &M);
        int total = N*M;
        memset(dp, 0, sizeof(dp));
        dp[1][1][1] = 1.0;
        for (int i=1;i<=N;++i)
            for (int j=1;j<=M;++j)
                for (int k=max(i,j); k<=i*j; ++k) {
                    if (i==N && j==M) break;
                    double cur = dp[i][j][k];
                    if (cur == 0) continue;
                    int rem = total - k;
                    // 1. 旧行旧列
                    if (k < i*j) dp[i][j][k+1] += cur * (i*j - k) / rem;
                    // 2. 新行旧列
                    if (i < N) dp[i+1][j][k+1] += cur * ((N-i)*j) / rem;
                    // 3. 旧行新列
                    if (j < M) dp[i][j+1][k+1] += cur * (i*(M-j)) / rem;
                    // 4. 新行新列
                    if (i

复杂度

状态数：O(N·M·N·M) ≤ 50⁴ = 6.25e6
转移 O(1)，总计 ~1e7 操作，8s 内通过


关键优化

k 下界：max(i,j)（至少覆盖行列数）
k 上界：i*j（最多填满交叉）
终止条件：maxK = max(N(M-1), M(N-1))+1（覆盖全棋盘所需最多子数）