SRM 620 Div2 Hard: RandomGraph 機率動態規劃解法詳解

題目背景與核心思路

這是一道經典的 TopCoder SRM 620 Div2 Level 3 題目 RandomGraph，核心考察機率動態規劃。題目要求計算在隨機圖中「至少存在一個大小大於 4 的連通元件」的機率。直接計算「至少一個」較為複雜，關鍵在於將條件轉化為互補事件：「所有連通元件的大小都小於等於 3」。透過這一轉換，問題便轉化為計算圖中所有連通塊大小均不超過 3 的機率，再用 1 減去該機率即得答案。

狀態定義與轉移

定義三維 DP 狀態 dp[a][b][c]，分別表示當前圖中：

• a：大小為 1 的連通元件（孤立點）的數量
• b：大小為 2 的連通元件（邊）的數量
• c：大小為 3 的連通元件（三角形或路徑）的數量

剩餘未處理的點數為 r = n - (a + 2b + 3c)。當 r = 0 時，所有點皆已分配完畢，滿足條件，機率為 1。

轉移邏輯

每一步從剩餘的 r 個點中選取新點加入圖中，並考慮其與現有元件的連邊情況（每條邊以機率 p 存在）：

1. 新點保持孤立：與所有現有點均無連邊，機率 (1-p)^(a+2b+3c)，狀態轉為 (a+1, b, c)。
2. 新點與一個孤立點相連：形成一個大小為 2 的元件，需選擇 1 個孤立點（a 種選法），連邊存在、其餘無連邊，機率 a * p * (1-p)^(a+2b+3c-1)，狀態轉為 (a-1, b+1, c)。
3. 新點與兩個孤立點相連：形成一個大小為 3 的元件，需選擇 2 個孤立點（C(a,2) 種選法），兩條連邊均存在、其餘無連邊，機率 C(a,2) * p^2 * (1-p)^(a+2b+3c-2)，狀態轉為 (a-2, b, c+1)。
4. 新點與一個大小為 2 的元件相連：形成大小為 3 的元件，需選擇 1 個大小-2 元件（b 種選法），且新點至少與該元件中的一個點相連（兩種情況：僅連一點、或連兩點），合併計算機率後狀態轉為 (a, b-1, c+1)。

完整 C++ 實現

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

double dp[51][51][51];
bool solved[51][51][51];

class RandomGraph {
public:
    int n;
    double p;

    double rec(int a, int b, int c) {
        double &res = dp[a][b][c];
        if (solved[a][b][c]) return res;
        int r = n - (a + 2*b + 3*c);
        if (r == 0) {
            solved[a][b][c] = true;
            return res = 1.0;
        }
        res = 0.0;
        // 新點孤立
        res += pow(1-p, a + 2*b + 3*c) * rec(a+1, b, c);
        // 新點與一個孤立點相連
        if (a >= 1) {
            res += pow(1-p, a + 2*b + 3*c - 1) * a * p * rec(a-1, b+1, c);
        }
        // 新點與兩個孤立點相連
        if (a >= 2) {
            res += pow(1-p, a + 2*b + 3*c - 2) * p * p * a * (a-1) / 2 * rec(a-2, b, c+1);
        }
        // 新點與一個大小為2的元件相連
        if (b >= 1) {
            res += pow(1-p, a + 2*b + 3*c - 1) * p * 2 * b * rec(a, b-1, c+1);
            res += pow(1-p, a + 2*b + 3*c - 2) * p * p * b * rec(a, b-1, c+1);
        }
        solved[a][b][c] = true;
        return res;
    }

    double probability(int n, int p) {
        this->n = n;
        this->p = p / 1000.0;
        memset(solved, 0, sizeof(solved));
        return 1.0 - rec(0, 0, 0);
    }
};

複雜度分析

狀態數上界為 O(n^3)（實際上 a+2b+3c ≤ n），每狀態轉移 O(1)，總時間複雜度 O(n^3)，空間複雜度 O(n^3)，滿足 n ≤ 50 的限制。

總結

本題展示了如何將「至少存在」類條件轉化為互補事件，並利用連通元件大小分類建立 DP 狀態，結合機率獨立性進行狀態轉移。這類「隨機圖連通元件統計」問題是機率 DP 的經典範疇，掌握狀態設計與互補轉化技巧至關重要。