hihoCoder 1075 開鎖魔法III：動態規劃與組合數學解析

題目背景

崔克茜在小馬鎮表演開鎖魔法：舞台上有 n 個盒子，每個盒子裡裝著一把鑰匙，且每個盒子只能被唯一的一把鑰匙打開。崔克茜隨機選擇 k 個盒子用魔法打開，求最終所有盒子都能被打開的概率。

核心觀察

1. 循環結構：打開一個盒子後，裡面的鑰匙會指向下一個盒子，形成一條鏈。因為每個盒子只有唯一對應的鑰匙，這鏈最終必定會回到起點，構成一個循環。整個盒子集合可分解為若干不相交的循環。
2. 可行條件：若循環總數為 num，則必須 k ≥ num，否則至少有一個循環完全無法被打開，概率為 0。
3. 計數方法：總方案數為 C(n, k)。可行方案數需從每個循環中至少選一個盒子，且總共選 k 個。這是一個經典的分組選擇問題，可用動態規劃求解。

動態規劃設計

設 dp[i][j] 表示從前 i 個循環中選取 j 把鑰匙的方案數。轉移方程：

dp[i][j] += dp[i-1][j-use] * C(cnt_i, use)

其中 cnt_i 為第 i 個循環的長度，use 從 1 到 min(cnt_i, j) 遍歷。初始 dp[0][0] = 1。

最終答案為 dp[num][k] / C(n, k)。為避免精度問題，組合數與 DP 值均用 double 儲存。

算法複雜度

• 找循環：O(n)
• 預計算組合數：O(n²)（n ≤ 300）
• DP：O(num * k * max_cycle)，最壞 O(n³)，但實際較小。

參考代碼 (C++)

#include <iostream>
#include <cstring>
#include <vector>
#include <iomanip>
using namespace std;

const int MAXN = 320;
double C[MAXN][MAXN];
bool vis[MAXN];
double dp[MAXN][MAXN];
vector loops;

void initComb() {
    for (int i = 0; i <= 300; ++i) {
        C[i][0] = C[i][i] = 1.0;
        for (int j = 1; j < i; ++j)
            C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
}

int main() {
    initComb();
    int T; cin >> T;
    while (T--) {
        int n, k; cin >> n >> k;
        vector match(n+1);
        for (int i = 1; i <= n; ++i) cin >> match[i];

        loops.clear();
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; ++i) if (!vis[i]) {
            int cnt = 0, cur = i;
            while (!vis[cur]) {
                vis[cur] = true;
                ++cnt;
                cur = match[cur];
            }
            loops.push_back(cnt);
        }

        int num = loops.size();
        if (k < num) {
            cout << fixed << setprecision(9) << 0.0 << '\n';
            continue;
        }

        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1.0;
        for (int i = 0; i < num; ++i) {
            for (int j = 0; j <= k; ++j) if (dp[i][j] > 0) {
                for (int use = 1; use <= loops[i] && j+use <= k; ++use) {
                    dp[i+1][j+use] += dp[i][j] * C[loops[i]][use];
                }
            }
        }
        cout << fixed << setprecision(9) << dp[num][k] / C[n][k] << '\n';
    }
    return 0;
}

總結

本題巧妙結合了置換群的循環分解與分組背包型 DP。關鍵在於識別「至少每個循環選一個」的條件，並用乘法原理在 DP 中累積方案數。注意雙精度處理可避免大數組合溢出與精度損失。