Codeforces 513G 逆序對期望：概率 DP 狀態壓縮轉移

問題描述

給定 n 個數的排列，進行 k 次操作：每次等概率隨機選擇一個區間 [l, r] 並翻轉。求 k 次操作後逆序對數量的期望值。n ≤ 100, k ≤ 100。

核心建模

定義 dp[i][j] 表示第 i 個元素在第 j 個元素之前的概率（i < j）。初始狀態：按原排列設置 dp[i][j] = 1 或 0。每次翻轉區間 [x, y] 會交換區間內元素相對位置，導致概率轉移。

狀態轉移推導

對於任意元素對 (i, j)，翻轉區間 [x, y] 後其新位置 (a, b) 為：

• 若 i ∈ [x, y]，則 a = x + y - i（鏡像位置）
• 若 j ∈ [x, y]，則 b = x + y - j

若區間包含 i, j 兩者，則相對順序翻轉，概率變為 1 - dp[i][j]；否則保持不變。遍歷所有可能區間，按概率 1/(n(n+1)/2) 累加轉移。

優化代碼實現（C++）

const int N = 105;
double dp[N][N], tmp[N][N];
int a[N];

int main() {
    int n, m;
    while (cin >> n >> m) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j)
                dp[i][j] = 1.0; // 初始有序對概率為 1

        double P = 2.0 / (n * (n + 1)); // 區間選中概率
        while (m--) {
            memcpy(tmp, dp, sizeof(dp));
            memset(dp, 0, sizeof(dp));
            for (int x = 1; x <= n; ++x)
                for (int y = x; y <= n; ++y) {
                    for (int i = 1; i <= n; ++i)
                        for (int j = i + 1; j <= n; ++j) {
                            int u = i, v = j;
                            if (x <= u && u <= y) u = x + y - u;
                            if (x <= v && v <= y) v = x + y - v;
                            if (u > v) swap(u, v);
                            if (x <= i && j <= y) // 區間包含 i,j 完整翻轉
                                dp[u][v] += (1 - tmp[i][j]) * P;
                            else
                                dp[u][v] += tmp[i][j] * P;
                        }
                }
        }
        double ans = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j)
                ans += (a[i] > a[j]) ? dp[i][j] : (1 - dp[i][j]);
        printf("%.10f\n", ans);
    }
    return 0;
}

複雜度分析

• 狀態數：O(n^2)
• 每步轉移：O(n^4) 暴力枚舉區間與元素對
• 總複雜度：O(k n^4)，n=100 時約 10^8 操作，需常數優化通過

關鍵優化技巧

• 使用 `memcpy` 快速複製數組
• 預計算區間選中概率 P
• 利用對稱性減少一半狀態（只存 i
• 內層循環優化：合併條件判斷，減少分支預測失敗

此題展示了概率 DP 在排列組合期望問題中的強大建模能力，狀態設計巧妙避免了直接模擬排列的指數狀態空間。